Greedy Algorithms
The Greedy Algorithms Pattern
Take the best-looking option at each step and never reconsider. Greedy produces short, fast solutions — but only for problems where the locally optimal choice is provably globally optimal, which is the part that has to be argued rather than assumed.
Interactive problems
Free to open
How do you recognise a greedy algorithms problem?
The problem asks for a maximum or minimum and there is a natural ordering that makes one choice obviously safest — earliest finishing time, largest value first. If a counterexample comes to mind quickly, the problem is dynamic programming instead.
What is the time complexity of the greedy algorithms pattern?
Typically O(n log n) for the sort plus O(n) for a single pass.
Greedy Algorithms practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Greedy Algorithms problems by difficulty and complexity
The difficulty, running time and extra space of every greedy algorithms solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Introduction to Greedy Algorithms | Easy | Ω(k log k) | Θ(k log k) | O(k log k) | O(1) |
| Best Time to Buy and Sell Stock | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| Gas Station | Medium | Ω(n) | Θ(n) | O(n) | O(1) |
| Jump Game | Medium | Ω(1) | Θ(n) | O(n) | O(1) |
Related patterns and concepts
The underlying technique is covered from first principles in the greedy algorithms lesson in the DSA visualizer curriculum. Greedy Algorithms is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree