Greedy Algorithms: Complete Guide with Code Examples

Greedy algorithms solve optimization problems by making the best local choice at every step and never revisiting it. You pick the option that looks best right now, update your state, and move on. Many interview problems that seem to require searching every combination, like which tasks to schedule or which trades to take, collapse into a single sorted pass once you see the greedy structure.

Definition: a greedy algorithm is a strategy that builds a solution step by step. At each step it commits to the locally optimal option and never undoes that choice. The strategy is only correct when the locally optimal option is also part of the globally optimal solution. That property has a name: the greedy choice property.

Real-World Analogy

Picture a dessert shop and a fixed budget. You want to leave with as many items as possible, and every item has a price. The greedy rule is simple. Always buy the cheapest remaining item. Each purchase shrinks the budget, and the cheapest item preserves the most budget for everything that comes after it.

Here is why that rule is safe. If an optimal shopping list somehow skipped the cheapest item, you could swap the cheapest item in for anything else on the list. The list stays valid and costs no more. This swap is called an exchange argument, and it is the same reasoning that proves greedy solutions on real interview problems.

Visual Explanation

Every greedy algorithm runs the same loop, regardless of the problem.

    graph TD
    A["Problem with options remaining"] --> B["Pick the locally best option"]
    B --> C["Apply it and update the state"]
    C --> D{"Is the problem solved?"}
    D -->|No| B
    D -->|Yes| E["Return the solution"]
  

The loop has three parts. First you identify the greedy choice, which is the locally best option among what remains. Then you apply it and update the state. Then you check whether the problem is solved.

What makes the loop fast is a second property, optimal substructure. After a greedy choice, what remains is a smaller instance of the same problem. You can apply the rule again on the remainder without looking back. The choice never constrains later steps in a harmful way.

When to Use This Pattern

These signals point to a greedy solution.

• The problem asks for a maximum or a minimum, and the locally best option is easy to name once the input is ordered. Interval scheduling takes the interval that ends earliest, then repeats.
• The answer never needs to undo an earlier choice. The moment a later decision invalidates an earlier one, this pattern is wrong for the problem.
• The input has a key you can sort by, like finish time, price, or value per unit. The sort is what turns the search into a single scan.
• The state you track is small, usually one or two values. Jump Game tracks only the furthest reachable index. Best Time to Buy and Sell Stock II tracks only a running profit.
• After a greedy choice, what remains is a smaller version of the same problem. That is optimal substructure, and it lets you repeat the rule on the remainder.

Complexity Analysis

Greedy algorithms have one of two cost profiles. A pure scan is linear. A sort-then-scan is dominated by the sort.

The scan itself is linear because each element is examined exactly once and the state updates in constant time. Sorting adds

Common Mistakes

These mistakes share a root cause: trusting the greedy rule before checking whether it is actually safe.

Applying greedy before testing a counterexample. The classic failure is coin change with denominations 1, 3, and 4 and a target of 6. Greedy takes a 4, then a 1, then a 1, which is three coins. Two 3s do the job with two coins. The greedy choice at the start blocks the better path. Before you commit to the strategy, hunt for a small input where the locally best choice leads to a worse total. If you find one, the problem belongs to dynamic programming.

Sorting by the wrong key. Interval problems sort by end time, not start time and not length. The earliest finish leaves the most room for later intervals, and that is exactly why the choice is optimal. To catch this in practice, run your ordering against a small input with a known answer. If the sort key is wrong, the result drifts off by one or two picks.

Missing the tie case. Several greedy formulas assume a unique best option. Task Scheduler is a good example. When two tasks tie for the most frequent, each one needs its own slot in the final frame, and the formula must count the ties. Test with a case where two candidates share the top value.

Confusing greedy with DP when the choice constrains later options. If a locally good choice can rule out a better global path, you need to compare whole paths, and that is DP territory. The tell is in the phrasing: does the current choice change what the later choices can be? If it does, ask yourself whether that change can ever hurt.

Related Patterns

• Dynamic Programming . Greedy is what you try before DP. When the locally best choice can block a better global path, DP is the fallback. The dynamic programming page covers the difference in detail.
• Interval Scheduling . Interval selection is the canonical greedy problem. It is where the exchange argument proof is usually taught, and it has its own pages here.
• Heap Priority Queue . Some greedy selections need the best remaining candidate on demand. A heap supplies that in
  O(log N)
  per step.
• Knapsack . Fractional knapsack is greedy by value per weight. The 0/1 version is DP. The contrast between the two shows exactly when greedy stops working.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.