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, amountPractise greedy
NeetCode 150 problems that use it
Greedy · Intervals ·
- LeetCode 53 · MediumMaximum Subarray (Kadane)The best winning streak in a trading diary
- LeetCode 55 · MediumJump GameA frog checking how far it could ever reach
- LeetCode 45 · MediumJump Game IIFewest hops, thinking one wave at a time
- LeetCode 134 · MediumGas StationA road trip around a ring of petrol stations
- LeetCode 846 · MediumHand of StraightsLaying a hand of cards out as runs
- LeetCode 1899 · MediumMerge Triplets to Form Target TripletMixing paint pots without overshooting a colour
- LeetCode 763 · MediumPartition LabelsCutting a ribbon so every letter stays in one piece
- LeetCode 678 · MediumValid Parenthesis StringBrackets with wildcard stars
- LeetCode 57 · MediumInsert IntervalSqueezing a new booking into a calendar
- LeetCode 56 · MediumMerge IntervalsMerging overlapping meetings into blocks
- LeetCode 435 · MediumNon-overlapping IntervalsCancelling the fewest bookings
- LeetCode 252 · EasyMeeting RoomsCan one person attend every meeting?
- LeetCode 253 · MediumMeeting Rooms IIHow many rooms does the office need?
- LeetCode 1851 · HardMinimum Interval to Include Each QueryThe shortest shift that covers each moment