Overview

A greedy algorithm builds a solution step by step, always taking the option that looks best right now. When it works, it is usually the simplest and fastest solution available: one pass, sometimes after a sort. The jump game, gas station and interval scheduling problems all have elegant greedy answers.

The danger is that greedy choices can be wrong. Paying 30 with coins {1, 15, 25} greedily uses 25 + 1×5 = six coins, while 15 + 15 uses two. The habit to build is a quick proof: an exchange argument (swapping any optimal solution's choice for the greedy one never makes it worse) or a "greedy stays ahead" argument. If you cannot find one, consider dynamic programming.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Single passO(n)
Sort then passO(n log n)
Greedy with a heapO(n log n)

Patterns to recognise

Reachability frontier

Use it for: Jump game I and II, video stitching.

Track the farthest index reachable; count a jump each time you pass the current frontier.

Running balance

Use it for: Gas station, lemonade change.

Track a running surplus; reset the start point when it goes negative.

Sort and match

Use it for: Assign cookies, boats to save people, hand of straights.

Sort both sides and pair smallest-with-smallest (or largest-with-smallest) using pointers.

Code template

Jump Game II — minimum jumps with a frontier
def jump(nums):
    jumps = 0
    current_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:            # must jump to go further
            jumps += 1
            current_end = farthest
    return jumps

Common mistakes

  • Trusting a greedy idea that only works on the sample — try to break it with a small counter-example first.
  • Sorting by the wrong key (start time instead of end time in interval scheduling).
  • Ties can matter; decide how equal keys should be ordered.

Quick check

Three questions on Greedy. Get all three right to earn +15 XP.

  1. A greedy algorithm makes which kind of choice at each step?

  2. Coins are 1, 3 and 4. Greedy "largest coin first" for amount 6 gives 4 + 1 + 1. What does this show?

  3. Which argument is commonly used to prove a greedy strategy correct?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Greedy?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor