What Is a Greedy Algorithm?

A greedy algorithm builds an answer in small irreversible steps. At each step it chooses the option that looks best according to a simple rule, such as the earliest finishing interval, the farthest reachable index, the cheapest available resource, or the lexicographically smallest character that can still lead to a valid answer. Once the choice is made, greedy commits and never revisits it.

That commitment is the entire attraction and the entire danger. If the local choice is safe, greedy can turn a large search space into a short scan, sort, or heap loop. If the local choice is only a tempting heuristic, the algorithm may be fast and consistently wrong. In interviews, the word greedy should immediately trigger the question: why is this local decision guaranteed not to block the global optimum?

Greedy is not the same as picking the first idea that seems intuitive. Many locally attractive decisions fail because they spend a scarce resource too early or ignore a future constraint. For example, with coin values 1, 3, and 4, making amount 6 by repeatedly taking the largest coin gives 4 + 1 + 1, but the optimum is 3 + 3. The local rule is simple, but it is not safe for that coin system.

Greedy is also not a substitute for dynamic programming. DP keeps multiple futures alive because early choices may interact with later choices in complicated ways. Greedy deliberately keeps only one future. That is acceptable only when a correctness argument shows that every optimal solution can be transformed to include the greedy choice without becoming worse.

A reliable greedy explanation has five parts:

1. State the objective: are you maximizing count, minimizing cost, reaching the end, or producing the smallest valid string?
2. Propose the greedy choice: which item or action do you commit to next?
3. Identify the ordering or data structure: sorting, two pointers, a heap, or a one-pass frontier.
4. Prove the choice is safe: usually with an exchange argument or an invariant.
5. Implement the scan and update the minimal state needed for future decisions.

This structure matters because greedy code is often short. Without the proof, short code looks like a guess. With the proof, the same code becomes an interview-ready algorithm.

Greedy problems often look complex because they contain many possible subsets, schedules, jumps, or strings. The winning insight is that the future can be summarized by a compact boundary: the current end time, the farthest reach, the number of open tasks, the best refund from a heap, or the last occurrence of a character. You do not need to remember every chosen item, only the state that determines what remains feasible.

That is why greedy solutions frequently have clean complexity: O(n log n) for sorting or heap operations, and O(n) once the order is fixed. The implementation may be simple, but the conceptual work is choosing a rule that preserves optimality under every possible input.