Greedy

A greedy algorithm builds a solution one step at a time, and at every step it commits to whatever choice looks best right now, without reconsidering that choice later and without exploring what would have happened had it chosen differently. There is no backtracking, no branching into alternate futures, no memo table of "what if." You walk through the input once, update a small amount of running state -- a running maximum, a running total, a count -- and by the time you reach the end, that state is the answer. This is what makes greedy algorithms so appealing: they are usually the simplest and fastest solutions available for a problem, often a single O(n) or O(n log n) pass with O(1) extra bookkeeping.

The catch is that "make the locally best choice" is not a proof technique -- it is a bet. For most problems, chaining together locally optimal decisions does not produce a globally optimal result; you need dynamic programming or search to actually consider the alternatives you would otherwise throw away. Greedy only works on problems with special structure, and the two most common ways to check whether that structure exists are:

• An exchange argument. Take any hypothetical optimal solution that disagrees with the greedy choice at some step, and show you can swap in the greedy choice without making the solution worse. If that swap is always possible, the greedy choice is at least as good as any alternative, and by induction the whole greedy solution is optimal.
• A greedy-choice invariant. Identify a property that greedy maintains at every step (e.g., "the farthest index reachable so far accounts for every jump considered up to this point") and show that property alone is sufficient to guarantee correctness at the end, regardless of which specific sequence of choices produced it.

Skipping this check is the single most common way greedy solutions go wrong: the code runs, it looks reasonable, it even passes a few examples -- and then it silently produces a wrong answer on an input where the "obviously best" local choice turns out to foreclose a better global option. If you can't articulate why the locally best choice can never hurt you later, you probably don't have a greedy problem; you have a DP or backtracking problem wearing a greedy disguise.

That contrast with dynamic programming is worth making explicit. DP also breaks a problem into steps, but at each step it keeps track of multiple possible states (or explores multiple choices and caches the best result for each state) precisely because the locally best choice at one step can depend on decisions made later, or can be beaten by a different, less obviously appealing choice earlier on. Greedy throws that machinery away and keeps only one running value, betting that no other candidate could ever catch up. When that bet is justified, greedy is dramatically simpler and faster than the equivalent DP; when it isn't, greedy gives you a fast, clean, wrong answer.

A generic template for a single-pass greedy solution looks like this:

best_so_far = initial_value
for item in input:
    best_so_far = combine(best_so_far, item)
    if best_so_far violates_constraint:
        return failure  # or adjust state and keep going
return success  # or return best_so_far

The specific "combine" step changes per problem -- tracking the farthest reachable index, tracking a running fuel budget, comparing a rating to its neighbor -- but the shape is always: one pass, one (or a small constant number of) running values, no revisiting of earlier decisions.

Complexity. Because greedy algorithms typically make a single pass over the input (sometimes preceded by a sort, which costs O(n log n)), the usual complexity is O(n) or O(n log n) time with O(1) extra space beyond the input and output. This efficiency is exactly why interviewers like greedy problems: they reward recognizing the right invariant rather than writing a lot of code.

Common pitfalls. The biggest one is assuming a problem is greedy when it actually requires DP or exhaustive search -- always sanity-check with a small counterexample before committing. A close second is choosing the wrong greedy criterion: sorting by the wrong key, or optimizing for the wrong quantity at each step, produces code that looks identical in structure to a correct greedy solution but silently returns a suboptimal or outright wrong answer. When in doubt, try to break your own greedy rule with a small, adversarial example before trusting it.

This subject walks through three classic greedy interview problems:

1. Jump to the End -- decide whether you can reach the last index of an array using a "farthest reachable" tracker.
2. Gas Stations -- find the starting index of a circular route that can be completed without running out of fuel, in one pass.
3. Candies -- distribute the minimum number of candies across a line of children satisfying a "higher rating gets more" rule, using a two-pass greedy.