Coding

Greedy

An algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate and obvious benefit (local optimum) with the hope that these choices lead to a global optimum.

Cheat Sheet

Prime Use Case

Use when the problem exhibits the 'Greedy Choice Property' and 'Optimal Substructure', typically involving optimization (min/max) over intervals, weights, or frequencies.

Critical Tradeoffs

  • Time Complexity: Usually O(N log N) due to sorting or O(N) with a heap.
  • Space Complexity: Often O(1) or O(N) for sorting/storage.
  • Correctness: Extremely fast but risky; it does not work for all optimization problems.

Killer Senior Insight

Greedy is effectively Dynamic Programming where the state transition is so constrained that you only ever need to explore a single path in the decision tree.

Recognition

Common Interview Phrases

The problem asks for the 'maximum number of non-overlapping' items.
The problem involves 'minimizing the number of' resources used (e.g., meeting rooms, taps).
The constraints are too large for O(N^2) DP, suggesting an O(N log N) sorting-based approach.
The problem involves fractional components (e.g., Fractional Knapsack).

Common Scenarios

  • Interval Scheduling and Partitioning.
  • Minimum Spanning Trees (Kruskal's and Prim's).
  • Single-Source Shortest Paths (Dijkstra's).
  • Huffman Coding for data compression.
  • Gas Station / Jump Game problems.

Anti-patterns to Avoid

  • 0/1 Knapsack Problem (requires DP because items are indivisible).
  • Finding the longest path in a graph (requires DP or exhaustive search).
  • Coin Change problem with non-canonical denominations (e.g., coins of 1, 3, 4 for a target of 6).

The Problem

The Fundamental Issue

Eliminates the need to explore an exponential number of combinations by making an irreversible, locally optimal decision at each step.

What breaks without it

Time Limit Exceeded (TLE) due to O(2^N) backtracking or O(N^2) DP.

Memory Limit Exceeded (MLE) from large DP tables.

Why alternatives fail

Dynamic Programming computes solutions to all subproblems, which is redundant if a greedy choice can be proven to stay ahead of any other choice.

Mental Model

The Intuition

Imagine climbing a mountain by always taking the steepest step available from your current position. If the mountain is a simple cone (convex), you reach the top. If it has multiple peaks (non-convex), you might get stuck on a smaller hill.

Key Mechanics

1

Sort the input based on a specific criteria (start time, end time, ratio).

2

Iterate through the sorted elements.

3

Make a locally optimal choice that is 'safe' (doesn't preclude the global optimum).

4

Update the current state and never revisit the decision.

Framework

When it's the best choice

  • When the problem has the 'Stay Ahead' property (the greedy choice is at least as good as any other choice at every step).
  • When the problem can be modeled as a Matroid.

When to avoid

  • When a local choice limits future options in a way that cannot be recovered.
  • When the problem requires looking ahead to see the impact of a current choice.

Fast Heuristics

If N > 10^5, look for Greedy or O(N log N) sorting.
If the problem involves 'subsets' and 'weights', check if it's 0/1 (DP) or Fractional (Greedy).

Tradeoffs

+

Strengths

  • High performance and low memory overhead.
  • Simpler implementation compared to complex DP transitions.
  • Often the only viable approach for massive datasets.
−

Weaknesses

  • Hard to prove correctness during an interview.
  • Very sensitive to the sorting criteria (e.g., sorting by start time vs. end time).
  • Brittle; small changes in constraints can make the greedy approach invalid.

Alternatives

Dynamic Programming
Alternative

When it wins

When subproblems overlap and the local optimum does not guarantee the global optimum.

Key Difference

DP considers all possible previous states to make the current decision; Greedy only considers the current state.

Backtracking
Alternative

When it wins

When you need to find all possible solutions or when the search space is small.

Key Difference

Backtracking explores all paths and 'undoes' choices; Greedy never looks back.

Execution

Must-hit talking points

  • Explicitly state the 'Greedy Choice Property' you are using.
  • Briefly explain why a local optimum leads to a global one (e.g., 'By picking the interval that ends earliest, we maximize the remaining time for other intervals').
  • Discuss the sorting criteria and its complexity.

Anticipate follow-ups

  • Q:How would you prove this is optimal? (Proof by Contradiction or Exchange Argument).
  • Q:What happens if the constraints change (e.g., items have values instead of just counts)?
  • Q:Can this be parallelized?

Red Flags

Sorting by the wrong attribute.

Why it fails: In interval scheduling, sorting by start time or shortest duration fails; only sorting by end time is globally optimal.

Assuming Greedy works for the Coin Change problem.

Why it fails: Greedy only works for 'canonical' coin systems (like US currency). For arbitrary sets, it fails to find the minimum number of coins.