Greedy

Core Concepts

Greedy algorithm — A problem-solving strategy that builds a solution incrementally by making the locally optimal choice at each step, never reconsidering past decisions, and expecting those local choices to produce a globally optimal result.

Greedy choice property — The global optimum can always be reached by making the locally optimal (greedy) choice at each step. This must be proven for correctness, not assumed.

Optimal substructure — An optimal solution to the whole problem contains optimal solutions to its subproblems. Greedy shares this with DP, but greedy never needs to examine multiple subproblem choices.

Exchange argument — The standard proof technique: assume an optimal solution differs from the greedy solution, then show swapping one element to match the greedy choice does not worsen the result. Repeat until both solutions are identical. Establishes the greedy choice property.

Greedy vs DP distinction — DP explores all subproblem combinations and takes the best; greedy commits to one branch and never revisits. Greedy is valid only when no future choice can invalidate the current one.

Inductive correctness — Greedy algorithms are typically proved by induction: the greedy choice is safe for the first step, and if it's safe for the first k steps, it's safe for k+1.

Greedy stays ahead — An alternative proof strategy: show that at every step the greedy solution is at least as good as any other partial solution (e.g., covers at least as many intervals, earns at least as much profit).

Scheduling / interval problems — The most common greedy domain. Problems reduce to: given a set of tasks/intervals with weights or deadlines, select or order them to optimize a metric.

Matroid — An abstract structure that characterises exactly when greedy produces a globally optimal solution. A set system is a matroid if and only if greedy on it (with any weight function) gives the optimal independent set. Knowing this prevents wasted attempts to apply greedy where it cannot work.

---

Types / Variants

---

Key Algorithms

Activity Selection (Earliest Finish Time)

Select the maximum number of non-overlapping intervals from a set.
Key insight: always picking the interval that ends earliest leaves the most room for future intervals.
Sort by end time; iterate, picking each interval whose start ≥ last chosen end.
Time O(n log n), space O(1).

Fractional Knapsack

Maximise value subject to weight capacity when items can be split.
Key insight: take items in order of decreasing value/weight ratio; split the last item if needed.
Sort by ratio descending; greedily fill capacity.
Time O(n log n), space O(1).
(0-1 Knapsack is NOT solvable by greedy — requires DP.)

Huffman Coding

Build an optimal prefix-free binary code minimising total encoded length.
Key insight: the two least-frequent symbols should be deepest in the tree (farthest from root); merge them first.
Use a min-heap; repeatedly merge the two smallest frequency nodes.
Time O(n log n), space O(n).

Job Scheduling with Deadlines (Maximize Profit)

Select at most one job per time slot to maximise profit, each job has a deadline.
Key insight: process jobs in decreasing profit order; greedily assign each to the latest available slot before its deadline.
Use a Union-Find to find the next free slot in O(α) per job.
Time O(n log n + n α(n)), space O(n).

Dijkstra's Algorithm

Single-source shortest paths on non-negative weighted graphs.
Key insight (greedy choice): the unvisited node with minimum tentative distance can never be relaxed further — it is finalised.
Min-heap extracts the best candidate; relax neighbours.
Time O((V + E) log V), space O(V + E).

See shortest-path.md for full coverage.

Kruskal's MST

Minimum spanning tree by greedily adding the cheapest edge that does not form a cycle.
Key insight (cut property): for any cut of the graph, the minimum-weight crossing edge is safe to include in some MST.
Sort edges by weight; use Union-Find to reject cycle-forming edges.
Time O(E log E), space O(V).

See graph-theory.md for full coverage.

Prim's MST

Minimum spanning tree by greedily expanding from a starting vertex.
Key insight: at each step, the cheapest edge crossing the cut between visited and unvisited vertices is safe.
Min-heap over crossing edges; extract minimum and add its endpoint.
Time O((V + E) log V) with binary heap, space O(V).

Gas Station (Circular Tour)

Find a starting station from which a car can complete a circular route.
Key insight: if total gas ≥ total cost, a solution always exists; start a new candidate whenever cumulative tank goes negative.
Single pass maintaining running sum and candidate start.
Time O(n), space O(1).

Jump Game (Can Reach End)

Determine if you can reach the last index given max-jump lengths.
Key insight: track the furthest reachable index; if current position exceeds it, you're stuck.
Time O(n), space O(1).

Jump Game II (Minimum Jumps)

Minimum number of jumps to reach the last index.
Key insight: at each "level" (current jump), record the furthest you can reach; jump when you exhaust the current level.
Implicit BFS / greedy level expansion.
Time O(n), space O(1).

Candy Distribution

Assign minimum candies to children in a line so each child with a higher rating than a neighbour gets more candies.
Key insight: two passes — left-to-right enforces the right-neighbour constraint; right-to-left enforces the left-neighbour constraint; take max at each position.
Time O(n), space O(n).

Assign Cookies

Maximise satisfied children by matching the smallest sufficient cookie to the least-greedy child.
Two-pointer after sorting both arrays.
Time O(n log n), space O(1).

Minimum Number of Platforms / Meeting Rooms II

Find peak simultaneous interval overlap.
Key insight: sort starts and ends separately; two-pointer sweep counts overlapping intervals at peak.
Time O(n log n), space O(1).

Task Scheduler (Cooldown)

Minimum time to execute all tasks with a cooldown n between same-task executions.
Key insight: the most frequent task is the bottleneck; the answer is max(n_tasks, (max_freq - 1) * (n + 1) + count_of_max_freq_tasks).
Time O(n), space O(1) (26 task types).

Remove K Digits (Lexicographically Smallest)

Remove exactly k digits to get the smallest number.
Key insight: maintain a monotone increasing stack; pop larger digits greedily when you still have removals left.
Time O(n), space O(n).

Largest Number

Arrange integers to form the largest number.
Key insight: custom comparator — a should precede b if str(a)+str(b) > str(b)+str(a).
Time O(n log n), space O(n).

Non-overlapping Intervals (Minimum Removals)

Remove minimum intervals to make the rest non-overlapping.
Key insight: identical to activity selection — count intervals NOT selected (earliest-end-first).
Time O(n log n), space O(1).

Partition Labels

Partition a string into as many parts as possible so each letter appears in at most one part.
Key insight: greedily extend the current partition to include the last occurrence of every character seen so far.
Time O(n), space O(26).

Boat to Save People

Minimum boats to rescue people (each boat carries ≤ 2, total weight ≤ limit).
Key insight: pair heaviest remaining with lightest if they fit; otherwise heaviest goes alone.
Two-pointer on sorted array.
Time O(n log n), space O(1).

Minimum Cost to Connect Ropes

Minimum cost to connect n ropes (cost = sum of two lengths).
Key insight: always merge the two shortest ropes first — equivalent to Huffman coding.
Min-heap; greedily merge.
Time O(n log n), space O(n).

---

Advanced Techniques

Greedy + Monotonic Stack

Solves: lex-min/max string construction, digit removal, duplicate-free subsequences.
Mechanism: maintain a stack with a monotone property; pop elements greedily when a "better" element arrives and a budget (removal count or occurrence count) allows.
When over simpler: use when the greedy decision depends on the relationship between the current element and previously committed elements, not just a global order. If a simple sort suffices, do not reach for this.
Time O(n), space O(n).

Greedy with Lazy Evaluation (Heap + Cancellation)

Solves: problems where the optimal action at time t can be "undone" by a better opportunity at time t' > t (e.g., buy/sell stock variants with transaction costs, minimum cost over a range).
Mechanism: instead of undoing a past decision explicitly, model the undo as a new virtual item in the heap. Classic example: push a negative profit whenever you "undo" a pick; this lets the algorithm greedily cancel prior commitments without O(n²) backtracking.
When over DP: use when the number of decisions is large and state space for DP is exponential; the heap models the state implicitly.
Time O(n log n), space O(n).

Exchange Argument as Design Tool

Solves: scheduling and ordering problems where the right sort key is not obvious.
Mechanism: suppose two adjacent items a, b can be swapped. Write cost(a before b) and cost(b before a); derive the inequality that makes a-before-b optimal; that inequality defines the comparator.
When over guessing: whenever you are unsure what to sort by — derive it formally rather than trying "sort by end time" vs "sort by duration" empirically.
No additional complexity beyond the sort.

Regret-Based Greedy (Undo via Virtual Items)

Solves: problems where a greedy pick may need to be reversed if a strictly better global assignment is found later (weighted bipartite matching, some scheduling problems).
Mechanism: when picking item x, also push a "regret item" of value −value(x) into the heap. If the algorithm later picks the regret item, it effectively unpicks x and uses the slot differently.
When over DP: when items arrive online or the state graph for DP is too large; regret items simulate an optimal look-ahead in O(log n) per step.
Time O(n log n), space O(n).

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Greedy on 0-1 Knapsack: the greedy ratio heuristic gives wrong answers when items cannot be split. Always check whether fractional splitting is allowed before applying greedy.

• Interval tie-breaking: when two intervals have the same end time, the choice between them is arbitrary for activity selection, but may matter for other variants (e.g., weighted intervals). Ensure your comparator is a total order to avoid undefined sort behavior.

• Circular problems (gas station): forgetting that the problem is circular leads to missed candidates. A single-pass linear scan works because the greedy observation (if total gas ≥ total cost, a solution exists) avoids brute-force wraparound checking.

• Exchange argument direction: when deriving a comparator, forgetting that the comparison must be a strict weak order (transitive, irreflexive) causes sort() to be undefined. Verify transitivity: if a < b and b < c under your comparator, then a < c.

• Empty or single-element input: activity selection, jump game, and interval removal should all short-circuit correctly for n ≤ 1. Off-by-one on the return value (returning 0 vs. 1) is common.

• Coin change and non-canonical systems: greedy (sort desc, take max) fails for arbitrary coin denominations (e.g., coins [1, 3, 4], amount 6 → greedy gives 4+1+1=3 coins, DP gives 3+3=2 coins). Greedy is correct only for canonical systems (like US coins).

• Task scheduler overcounting: counting max-frequency tasks incorrectly (especially ties) produces the wrong formula result. Recount carefully: count_max = number of tasks with frequency == max_freq.

• Monotonic stack budget undercount: after the main scan, if removals remain, they must be removed from the tail (rightmost digits / characters), not randomly. Forgetting this gives a wrong lexicographic result.

• Greedy on graphs with negative edges: Dijkstra's greedy finalisation is invalid with negative edge weights. Verify edge weights are non-negative before applying; otherwise use Bellman-Ford or SPFA.

• Huffman / merge cost accumulation: the cost of a merge is the sum of the two values merged, not their product or max. Misidentifying the cost function produces a wrong heap key.

---

Implementation Notes

• Python's heapq is a min-heap only; negate values to simulate a max-heap (heapq.heappush(h, -val)).
• Python's sort with a custom comparator requires functools.cmp_to_key; a raw lambda returning a - b does not work directly as a key function.
• For interval problems, represent intervals as tuples (start, end) so sorted() sorts by start by default; add end as a secondary key explicitly when needed.
• When using Union-Find for job scheduling slot assignment, initialise parent[i] = i for slots 0..max_deadline; find returns the next available slot; union(slot, slot-1) after use.
• Python recursion limit (default 1000) can be hit in recursive greedy tree-building (e.g., Huffman); use iterative heap-based construction instead.
• For the "Largest Number" comparator: return -1 if a+b > b+a else (1 if a+b < b+a else 0) where a, b are strings.
• math.inf (Python) or float('inf') works for sentinel values in greedy reach tracking; avoid using large integers that may cause overflow when added.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Interval Scheduling

• Activity Selection / Non-overlapping Intervals (LC 435)
• Minimum Number of Meeting Rooms (LC 253)
• Merge Intervals (LC 56)
• Minimum Number of Arrows to Burst Balloons (LC 452)
• Car Pooling (LC 1094)

Jump / Reach

• Jump Game (LC 55)
• Jump Game II (LC 45)
• Video Stitching (LC 1024)

Sequence / String Construction

• Remove K Digits (LC 402)
• Largest Number (LC 179)
• Create Maximum Number (LC 321)
• Remove Duplicate Letters (LC 316)
• Monotone Increasing Digits (LC 738)

Scheduling / Assignment

• Task Scheduler (LC 621)
• Candy (LC 135)
• Assign Cookies (LC 455)
• Gas Station (LC 134)
• Two City Scheduling (LC 1029)

Greedy on Arrays

• Partition Labels (LC 763)
• Boats to Save People (LC 881)
• Minimum Cost to Connect Sticks (LC 1167)
• Lemonade Change (LC 860)
• Queue Reconstruction by Height (LC 406)

Graph / MST (Greedy-based)

• Min Cost to Connect All Points (LC 1584) — Prim's / Kruskal's
• Network Delay Time (LC 743) — Dijkstra's
• Cheapest Flights Within K Stops (LC 787)

Hard

• IPO (LC 502) — greedy + two heaps
• Minimum Number of Refueling Stops (LC 871) — greedy + max-heap
• Course Schedule III (LC 630) — greedy + max-heap with regret
• Maximum Performance of a Team (LC 1383)
• Find the Most Competitive Subsequence (LC 1673)

Additional LeetCode Coverage

• Can Place Flowers (LC 605)
• Maximum 69 Number (LC 1323)
• Maximum Number of Non-Overlapping Substrings (LC 1520)
• Increasing Triplet Subsequence (LC 334)

Clarification Questions to Ask

• Can intervals be open or closed? Does touching count as overlapping?
• Are items/tasks divisible (fractional knapsack) or indivisible (0-1)?
• Is the coin/denomination system canonical, or arbitrary?
• Is the graph directed or undirected? Are edge weights guaranteed non-negative?
• What is the definition of "cost" in merge problems — sum, product, or max?
• Are there ties in ratings/priorities, and does tie-breaking matter for the answer?
• Is the schedule circular (gas station) or linear?

Common Interview Mistakes

• Applying greedy without verifying the greedy choice property, then being unable to explain why it's correct.
• Confusing 0-1 knapsack with fractional knapsack and applying the ratio heuristic incorrectly.
• Sorting by the wrong key (e.g., sorting by duration instead of end time for activity selection).
• Forgetting to handle leftover budget in monotonic-stack problems (remaining removals come from the tail).
• Off-by-one: returning 0 when the answer should be 1 for single-element inputs.
• Using Dijkstra's on a graph with negative edge weights and not catching the invalidity.
• Failing to justify the exchange argument when asked "why is your greedy correct?"

Typical Follow-Up Escalations

• "What if items have weights and you can't split them?" → Switch to 0-1 knapsack DP; greedy fails.
• "What if the graph has negative edges?" → Replace Dijkstra with Bellman-Ford or SPFA.
• "What if you want the k-th best solution, not just the best?" → Greedy no longer applies directly; use DP or priority-queue enumeration.
• "Can you do this in O(n) instead of O(n log n)?" → Ask whether input is already sorted; if so, sorting step drops out.
• "What if tasks can have dependencies?" → Greedy alone is insufficient; combine with topological sort (see graph-theory.md).
• "Prove your greedy is optimal." → Walk through the exchange argument: assume the optimal solution differs at the first step, swap to match greedy, show the result is no worse.