0
Challenge · 71Greedy, Bits & Math
Choosing greedy, DP or brute force
Techniquesused in ~85% of apps
You now know enough techniques that the hard part has moved. It is no longer how to write a solution, it is deciding which one before you have written anything. This is the decision an interviewer is actually watching you make.
Core idea. Read the constraints to rule approaches out, then ask one question: does a locally best choice ever close off a better future? If it provably never does, greedy. If it can, dynamic programming. If the input is tiny, brute force is a correct answer you can produce immediately and improve from.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
the same instinct, on a problem where it loses
greedy: biggest coin that fits
nothing yet
still to pay
11
the actual best
56
coins used
2
make 11 from 1, 5, 6, 9. The instinct: take the biggest coin that fits
step 1 of 5
Same instinct, and it loses by a whole coin. Greedy needs an argument for why a locally best choice cannot close off a better future, and here there is none.
↑ play a little first, then dig in