Math for coding interviews/Local vs global optimum
Greedy Algorithms: Local vs Global Optimum
A local optimum is the best choice right now. A global optimum is the best choice for the entire problem. Greedy algorithms always pick the local optimum at each step and hope (or can prove) this leads to the global optimum. Sometimes it works, sometimes it does not.
See it for yourself
A landscape of hills. The global maximum is the tallest peak. A local maximum is any peak where the ground slopes down in all directions - but it might be a small hill with a bigger mountain nearby. Greedy always climbs the steepest nearby slope.
Local vs global optimum
A local optimum is the best choice right now. A global optimum is the best choice for the entire problem. Greedy algorithms always pick the local optimum at each step and hope (or can prove) this leads to the global optimum. Sometimes it works, sometimes it does not.
Think of it this way: Hiking to the tallest mountain. If you always walk uphill, you might reach the top of a small hill and get stuck. To find the tallest peak, sometimes you have to go downhill first (which greedy never does).
For algorithms: Knowing when greedy works (interval scheduling, Huffman coding, Dijkstra) vs when it fails (coin change with arbitrary denominations, general knapsack) is the key insight for this category.
Real-world analogy
Hiking to the tallest mountain. If you always walk uphill, you might reach the top of a small hill and get stuck. To find the tallest peak, sometimes you have to go downhill first (which greedy never does).
Why it matters in interviews
Knowing when greedy works (interval scheduling, Huffman coding, Dijkstra) vs when it fails (coin change with arbitrary denominations, general knapsack) is the key insight for this category.