A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a global optimum. It is simple and fast, but only correct when the problem has the greedy-choice property and optimal substructure.
Never reconsider past choices — commit to the best immediate option and move on.
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
This is optimal for US coins, but fails for sets like {1, 3, 4} where greedy gives 4+1+1 for 6 instead of 3+3.
Examples that work: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Usually fast — often O(n log n) after sorting.
Greedy is not always correct. Prove the greedy-choice property or test against a brute-force/DP baseline before trusting it.
When greedy applies, it is far simpler and faster than DP or brute force.
Knowing when it is valid — and when it silently gives wrong answers — is a mark of algorithmic maturity.
Many cornerstone graph algorithms are greedy at heart.
A library of IT interview questions with detailed answers — from Junior to Senior.
Donate