Core pattern

Greedy: paying with the biggest coin that fits

Learn the greedy pattern through one picture you won’t forget, worked on Coin change, greedy version.

The example problem

Pay an amount using the fewest coins and notes, given a currency system like Indian rupees (50, 20, 10, 5, 2, 1).

Input:  ₹87 with [50, 20, 10, 5, 2, 1]
Output: 5 pieces   (50 + 20 + 10 + 5 + 2)

Picture it

Picture a cashier paying from a drawer. They always grab the biggest note or coin that doesn’t exceed what’s still owed, then repeat with the remainder. For normal currencies this greedy choice is always best. (For strange coin sets like [1, 3, 4] it can fail: see Coin Change for the DP fix.)

The key idea

Greedy: take the largest piece that fits. Correct for “canonical” coin systems only.

Python

def pay(amount, coins):        # coins: biggest first
    used = []
    for c in coins:
        while amount >= c:
            amount -= c
            used.append(c)
    return used, amount

Practise greedy

NeetCode 150 problems that use it

Greedy · Intervals ·