What is a Greedy Algorithm?
A greedy algorithm makes the best safe choice available now and never revisits that choice. The difficult part is proving that the choice cannot block a better final answer.
You need sorting, loops, and a basic understanding of optimal solutions. The short version is: commit to a local choice only when you can explain why some optimal answer can always include it.
The Core Idea: Take Safe Progress
In LC 122: Stock Trading, prices are [7,1,5,3,6,4].
We can earn 4 from the rise 1 to 5 and 3 from the rise 3 to 6.
Why is it safe to collect every positive one-day increase? A long rise has the same profit as the sum of its daily rises. Collecting each positive step cannot lose profit.
It is like walking uphill with an elevation tracker. Adding every upward metre gives the same total climb as measuring each complete hill from bottom to top.
How Positive Gains Add Up
The Rule You Keep True
After processing each position, the stored result must be as good as any result possible using only the processed prefix. The exact proof changes with the greedy rule.
Common shapes include:
- Collect every safe gain for Stock Trading.
- Keep the farthest reachable boundary for Jump Game.
- Choose the earliest finishing option for interval scheduling.
- Cancel opposing votes to retain a majority candidate.
Gas Station is the one that usually trips us up. When the running fuel becomes negative, none of the stations since the current start can be a valid start. Resetting after that failure is safe because every one of those candidates shares the same failed prefix.
Picking the Right Shape
From Rule to Code
- State the local choice in one sentence.
- Explain why replacing a different choice with this one cannot worsen an optimal answer.
- Sort the input if the proof needs a particular order.
- Scan once while keeping only the summary needed for the next choice.
- Return the accumulated result or verify the final candidate.
The scan finishes after each item is considered once, so these examples take O(n) time after any required sort.
When to use it
- •A locally best choice can be proven safe and never needs to be undone.
- •The problem asks for a maximum, minimum, or feasible result over an ordered sequence.
- •Keeping only the best summary so far is enough for future decisions.
- •Sorting exposes a natural order in which choices can be committed.
How to identify it
- •The prompt asks for the most, least, earliest, or fewest under simple constraints.
- •A choice can be exchanged with another without making an optimal solution worse.
- •Future input cannot make the current safe choice harmful.
- •A one-pass rule appears to replace a larger table of subproblems.
Key insights
- →A greedy rule needs a reason that the local choice belongs to some optimal solution.
- →Stock Trading can collect every positive day-to-day increase because those gains combine into the same total as longer trades.
- →Boyer-Moore voting cancels different values so a true majority remains as the candidate.
- →Sorting often turns a global scheduling problem into a sequence of safe local decisions.
- →Greedy algorithms usually keep a small summary rather than every earlier choice.
Common mistakes
- 01Choosing the value that looks best now without proving that it is safe.
- 02Using a greedy rule on a problem where a later choice can make an earlier choice wrong.
- 03Treating the Boyer-Moore candidate as guaranteed when the prompt does not promise a majority.
- 04Adding only one large stock increase and missing several separate profitable rises.
- 05Sorting by the wrong endpoint in an interval scheduling problem.