Imagine you're at a buffet. You look at the spread, and your strategy is simple: **grab the best thing you can see right now**. Don't plan ahead. Don't worry about what's coming next. Just take what looks optimal at this moment, then move on and repeat. That's a greedy algorithm. At every step, you make the **locally optimal choice** — the best decision you can make right now — and you never look back. No recursion trees. No memoization tables. No backtracking. You commit to each decision and move forward. And here's the wild part: sometimes, this reckless-sounding strategy produces the **globally optimal answer**. Not just a good answer. The *best possible* answer. It sounds like it shouldn't work, and yet for the right problems, it's mathematically provable. But there's a catch. A big one. **Greedy doesn't always work.** For some problems, the locally optimal choice leads you straight off a cliff. Making the best decision at each step can paint you into a corner where the overall solution is terrible. Knowing *when* greedy works — and when you need to reach for dynamic programming instead — is the real skill. That's what separates someone who "knows greedy" from someone who can actually solve problems with it. > "A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit." This guide will teach you the intuition behind greedy algorithms, give you a framework for recognizing greedy problems, walk you through every major greedy pattern with TypeScript solutions, and — crucially — teach you how to tell when greedy works and when it doesn't. Let's go. --- ## The Big Idea: Why Greedy Works (When It Works) Greedy algorithms rest on two pillars. If a problem has both of these properties, greedy will give you the optimal answer: ### 1. Greedy Choice Property You can build a globally optimal solution by making locally optimal choices. The choice you make at each step doesn't need to depend on future choices — you can commit to what looks best *right now* and still end up with the best overall answer. ### 2. Optimal Substructure After making a greedy choice, the remaining problem is a smaller instance of the same problem. The optimal solution to the whole problem contains optimal solutions to the subproblems. > If you can prove these two properties hold, greedy is guaranteed to work. If you can't, it probably doesn't. ### The Classic Analogy: Making Change You're a cashier and you need to give someone 41 cents in change. You want to use the **fewest coins possible**. With US denominations [25, 10, 5, 1], what do you do? 1. Grab the biggest coin that fits: **25¢** → remaining: 16¢ 2. Grab the biggest coin that fits: **10¢** → remaining: 6¢ 3. Grab the biggest coin that fits: **5¢** → remaining: 1¢ 4. Grab the biggest coin that fits: **1¢** → remaining: 0¢ **4 coins: [25, 10, 5, 1]**. That's optimal. The greedy approach works perfectly here because of the specific structure of US coin denominations — each denomination is a multiple or near-multiple of the smaller ones, so grabbing the biggest first always leads to the fewest total. But change the denominations to **[1, 3, 4]** and try to make **6 cents**: - Greedy: grab 4 → remaining 2 → grab 1 → grab 1 → **3 coins: [4, 1, 1]** - Optimal: **2 coins: [3, 3]** Greedy fails. The locally optimal choice (grab the biggest coin) leads to a suboptimal global solution. For this problem with arbitrary denominations, you need **dynamic programming**. This one example captures the entire challenge of greedy algorithms: they're elegant and fast when they work, but you need to verify the greedy choice property holds before trusting them. --- ## The Greedy Framework Almost every greedy problem follows the same skeleton: ### Step 1: Sort the Input Most greedy problems require sorting — by end time, by start time, by size, by frequency, by some custom criterion. The sorting step is what creates the structure that lets greedy work. ### Step 2: Iterate and Make the Locally Optimal Choice Walk through the sorted input. At each step, make the choice that looks best right now. This might mean "take the earliest ending interval," "jump as far as possible," or "assign the smallest sufficient resource." ### Step 3: Prove It Works This is the part most people skip — and it's the most important. You need an argument for why the greedy choice is safe. The two most common proof techniques: - **Exchange argument**: Assume an optimal solution makes a different choice. Show that swapping to the greedy choice doesn't make things worse (and might make them better). Therefore, an optimal solution that includes the greedy choice must exist. - **Greedy stays ahead**: Show that at every step, the greedy solution is at least as good as any other solution. It "stays ahead" and never falls behind. You won't need formal proofs in interviews, but having the intuition for *why* greedy works on a given problem is critical for explaining your approach. ```typescript function greedyTemplate(input: any[]): any { // Step 1: Sort by the relevant criterion input.sort((a, b) => a.key - b.key); let result = initialValue; // Step 2: Iterate and make the greedy choice for (const item of input) { if (isValid(item)) { result = update(result, item); } } return result; } ``` That's the skeleton. Now let's put meat on the bones. --- ## Pattern 1: Interval Scheduling — Greedy on Intervals Interval problems are the **bread and butter** of greedy algorithms. You're given a collection of intervals (meetings, events, tasks) and need to make optimal decisions about which to keep, merge, or count. The key insight is always about **sorting**. --- ### Non-overlapping Intervals (LeetCode 435) **Problem**: Given an array of intervals `[start, end]`, return the minimum number of intervals you need to remove to make the rest non-overlapping. **The Greedy Insight**: This is equivalent to finding the **maximum number of non-overlapping intervals** (then subtract from total). To maximize non-overlapping intervals, sort by **end time** and always pick the interval that ends earliest. Why? An interval that ends earlier leaves more room for future intervals. > Sort by end time. Always keep the interval that ends earliest. This is the classic "activity selection" problem — one of the first problems ever proven to have a greedy solution. ```typescript function eraseOverlapIntervals(intervals: number[][]): number { if (intervals.length === 0) return 0; intervals.sort((a, b) => a[1] - b[1]); let kept = 1; let prevEnd = intervals[0][1]; for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] >= prevEnd) { kept++; prevEnd = intervals[i][1]; } } return intervals.length - kept; } ``` **Walkthrough** with `[[1,2],[2,3],[3,4],[1,3]]`: ``` Sorted by end: [[1,2],[2,3],[1,3],[3,4]] Start: keep [1,2], prevEnd = 2, kept = 1 i=1: [2,3] start(2) >= prevEnd(2) → keep it, prevEnd = 3, kept = 2 i=2: [1,3] start(1) < prevEnd(3) → overlaps, skip i=3: [3,4] start(3) >= prevEnd(3) → keep it, prevEnd = 4, kept = 3 Kept 3 intervals → remove 4 - 3 = 1 ``` **Why sort by end time, not start time?** Consider `[[1,10],[2,3],[4,5]]`. Sorted by start, you might keep `[1,10]` first, which blocks everything else. Sorted by end, you keep `[2,3]` and `[4,5]` — two intervals instead of one. The earliest-ending interval is always the greediest choice because it minimizes the "damage" to future options. | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(1) | --- ### Merge Intervals (LeetCode 56) **Problem**: Given an array of intervals, merge all overlapping intervals. **The Greedy Insight**: Sort by start time, then iterate. If the current interval overlaps with the previous one (its start is ≤ the previous end), merge them by extending the end. Otherwise, start a new group. ```typescript function merge(intervals: number[][]): number[][] { if (intervals.length <= 1) return intervals; intervals.sort((a, b) => a[0] - b[0]); const merged: number[][] = [intervals[0]]; for (let i = 1; i < intervals.length; i++) { const last = merged[merged.length - 1]; const curr = intervals[i]; if (curr[0] <= last[1]) { last[1] = Math.max(last[1], curr[1]); } else { merged.push(curr); } } return merged; } ``` **Walkthrough** with `[[1,3],[2,6],[8,10],[15,18]]`: ``` Sorted: [[1,3],[2,6],[8,10],[15,18]] Start with merged = [[1,3]] i=1: [2,6] → 2 <= 3, overlap → extend to [1,6]. merged = [[1,6]] i=2: [8,10] → 8 > 6, no overlap → push. merged = [[1,6],[8,10]] i=3: [15,18] → 15 > 10, no overlap → push. merged = [[1,6],[8,10],[15,18]] ``` | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(n) | --- ### Insert Interval (LeetCode 57) **Problem**: Given a sorted list of non-overlapping intervals, insert a new interval and merge if necessary. **The Greedy Insight**: Divide the problem into three phases — intervals that come entirely before the new one, intervals that overlap (merge them), and intervals that come entirely after. ```typescript function insert(intervals: number[][], newInterval: number[]): number[][] { const result: number[][] = []; let i = 0; const n = intervals.length; // Phase 1: add all intervals that end before newInterval starts while (i < n && intervals[i][1] < newInterval[0]) { result.push(intervals[i]); i++; } // Phase 2: merge all overlapping intervals with newInterval while (i < n && intervals[i][0] <= newInterval[1]) { newInterval[0] = Math.min(newInterval[0], intervals[i][0]); newInterval[1] = Math.max(newInterval[1], intervals[i][1]); i++; } result.push(newInterval); // Phase 3: add all intervals that start after newInterval ends while (i < n) { result.push(intervals[i]); i++; } return result; } ``` **The three phases make this clean and intuitive**: before, overlap, after. No complex conditionals, no edge case nightmares. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(n) | --- ### Meeting Rooms II (LeetCode 253) **Problem**: Given an array of meeting intervals `[start, end]`, find the minimum number of conference rooms required. **The Greedy Insight**: Sort meetings by start time. Use a min-heap to track the earliest ending meeting across all rooms. If the next meeting starts after the earliest ending one, reuse that room. Otherwise, allocate a new room. ```typescript function minMeetingRooms(intervals: number[][]): number { if (intervals.length === 0) return 0; intervals.sort((a, b) => a[0] - b[0]); // Min-heap of end times (simulated with sorted array for clarity) const endTimes: number[] = []; const addToHeap = (val: number) => { endTimes.push(val); endTimes.sort((a, b) => a - b); }; const peekMin = () => endTimes[0]; const removeMin = () => endTimes.shift(); for (const [start, end] of intervals) { if (endTimes.length > 0 && peekMin()! <= start) { removeMin(); } addToHeap(end); } return endTimes.length; } ``` **Alternative — the sweep line approach** (often cleaner in interviews): ```typescript function minMeetingRoomsSweep(intervals: number[][]): number { const starts = intervals.map(i => i[0]).sort((a, b) => a - b); const ends = intervals.map(i => i[1]).sort((a, b) => a - b); let rooms = 0; let maxRooms = 0; let s = 0; let e = 0; while (s < starts.length) { if (starts[s] < ends[e]) { rooms++; s++; } else { rooms--; e++; } maxRooms = Math.max(maxRooms, rooms); } return maxRooms; } ``` > The sweep line approach separates starts and ends into two sorted arrays, then scans through events chronologically. A start means "need a room," an end means "free a room." The peak number of simultaneously needed rooms is your answer. | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(n) | --- ### Minimum Number of Arrows to Burst Balloons (LeetCode 452) **Problem**: Balloons are represented as intervals `[start, end]` on a wall. An arrow shot at position `x` bursts all balloons where `start <= x <= end`. Find the minimum number of arrows needed to burst all balloons. **The Greedy Insight**: This is Non-overlapping Intervals in disguise. Sort by end position. Shoot an arrow at the end of the first balloon. Any balloon whose start is ≤ this position gets burst by the same arrow. When you find a balloon that isn't burst, shoot a new arrow at its end. ```typescript function findMinArrowShots(points: number[][]): number { if (points.length === 0) return 0; points.sort((a, b) => a[1] - b[1]); let arrows = 1; let arrowPos = points[0][1]; for (let i = 1; i < points.length; i++) { if (points[i][0] > arrowPos) { arrows++; arrowPos = points[i][1]; } } return arrows; } ``` **Walkthrough** with `[[10,16],[2,8],[1,6],[7,12]]`: ``` Sorted by end: [[1,6],[2,8],[7,12],[10,16]] Arrow 1 at position 6: bursts [1,6] and [2,8] (both include 6) [7,12]: start(7) > 6 → new arrow needed Arrow 2 at position 12: bursts [7,12] and [10,16] (both include 12) Answer: 2 arrows ``` | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(1) | --- ## Pattern 2: Jump / Reachability Jump problems ask: "Can you reach the end? What's the fewest steps?" The greedy approach tracks how far you *can* reach and extends that frontier greedily. --- ### Jump Game (LeetCode 55) **Problem**: Given an array where each element represents the maximum jump length from that position, determine if you can reach the last index. **The Greedy Insight**: Track the **farthest reachable index**. At each position, update it. If you ever land on a position beyond your farthest reach, you're stuck. ```typescript function canJump(nums: number[]): boolean { let farthest = 0; for (let i = 0; i < nums.length; i++) { if (i > farthest) return false; farthest = Math.max(farthest, i + nums[i]); if (farthest >= nums.length - 1) return true; } return true; } ``` **Walkthrough** with `[2, 3, 1, 1, 4]`: ``` i=0: farthest = max(0, 0+2) = 2 i=1: farthest = max(2, 1+3) = 4 → 4 >= 4 → return true! ``` And with `[3, 2, 1, 0, 4]`: ``` i=0: farthest = max(0, 0+3) = 3 i=1: farthest = max(3, 1+2) = 3 i=2: farthest = max(3, 2+1) = 3 i=3: farthest = max(3, 3+0) = 3 i=4: i(4) > farthest(3) → return false ``` > The beauty of this solution is its simplicity. No BFS, no DP table, no recursion. One pass, one variable, O(n) time. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### Jump Game II (LeetCode 45) **Problem**: Given the same setup, find the **minimum number of jumps** to reach the last index. (You're guaranteed you can reach it.) **The Greedy Insight**: Think of it like BFS, where each "level" is a range of positions reachable in one jump. From the current level, find the farthest you can reach. When you exhaust the current level, increment jumps and move to the next level. ```typescript function jump(nums: number[]): number { let jumps = 0; let currentEnd = 0; let farthest = 0; for (let i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i === currentEnd) { jumps++; currentEnd = farthest; if (currentEnd >= nums.length - 1) break; } } return jumps; } ``` **Walkthrough** with `[2, 3, 1, 1, 4]`: ``` jumps=0, currentEnd=0, farthest=0 i=0: farthest = max(0, 0+2) = 2 i === currentEnd(0) → jumps=1, currentEnd=2 i=1: farthest = max(2, 1+3) = 4 i=2: farthest = max(4, 2+1) = 4 i === currentEnd(2) → jumps=2, currentEnd=4 4 >= 4 → break Answer: 2 jumps ``` > Think of `currentEnd` as the boundary of the "current level" in a BFS. When you hit the boundary, you advance to the next level. `farthest` is the boundary of the next level. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### Video Stitching (LeetCode 1024) **Problem**: Given clips `[start, end]` and a time `T`, find the minimum number of clips to cover `[0, T]`. **The Greedy Insight**: This is Jump Game II wearing a costume. Think of each clip as a "jump" from its start to its end. Sort clips by start time. From the current position, greedily pick the clip that extends farthest. It's the same BFS-level logic. ```typescript function videoStitching(clips: number[][], time: number): number { clips.sort((a, b) => a[0] - b[0] || b[1] - a[1]); let count = 0; let currentEnd = 0; let farthest = 0; let i = 0; while (currentEnd < time) { while (i < clips.length && clips[i][0] <= currentEnd) { farthest = Math.max(farthest, clips[i][1]); i++; } if (farthest === currentEnd) return -1; count++; currentEnd = farthest; } return count; } ``` **Walkthrough** with `clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10`: ``` Sorted: [[0,2],[1,9],[1,5],[4,6],[5,9],[8,10]] currentEnd=0: clips starting at 0 or earlier: [0,2],[1,9],[1,5] farthest = max(2,9,5) = 9 count=1, currentEnd=9 currentEnd=9: clips starting at 9 or earlier: [4,6],[5,9],[8,10] farthest = max(6,9,10) = 10 count=2, currentEnd=10 10 >= 10 → return 2 ``` | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(1) | --- ## Pattern 3: Scheduling / Assignment These problems involve assigning resources, scheduling tasks, or arranging elements optimally. The greedy strategy usually involves sorting by some clever criterion and then making simple assignments. --- ### Task Scheduler (LeetCode 621) **Problem**: Given tasks represented by characters and a cooldown period `n`, find the minimum time (intervals) to complete all tasks. The same task must be separated by at least `n` intervals. **The Greedy Insight**: The most frequent task is the bottleneck. Arrange tasks in "frames" of size `n + 1`. The most frequent task defines the frame count: `(maxFreq - 1)` complete frames, plus a final partial frame for all tasks that share the max frequency. ```typescript function leastInterval(tasks: string[], n: number): number { const freq: number[] = new Array(26).fill(0); for (const task of tasks) { freq[task.charCodeAt(0) - 65]++; } const maxFreq = Math.max(...freq); const maxCount = freq.filter(f => f === maxFreq).length; // (maxFreq - 1) full frames of size (n + 1), plus the final group const result = (maxFreq - 1) * (n + 1) + maxCount; // Can't be less than total tasks (when n is small enough) return Math.max(result, tasks.length); } ``` **The "Frame" Mental Model** for `tasks = ['A','A','A','B','B','B'], n = 2`: ``` maxFreq = 3 (both A and B appear 3 times) maxCount = 2 (A and B both have max freq) Frame layout (n+1 = 3 slots per frame): [A, B, _] [A, B, _] [A, B] frame 1 frame 2 final (3-1) * 3 + 2 = 8 tasks.length = 6 Answer: max(8, 6) = 8 ``` > Why take the `max` with `tasks.length`? When `n` is very small (or 0), there's no idle time needed, and the answer is simply the number of tasks. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### Assign Cookies (LeetCode 455) **Problem**: You have children with greed factors `g[i]` and cookies with sizes `s[j]`. A child is content if they get a cookie with size ≥ their greed factor. Maximize the number of content children. **The Greedy Insight**: Sort both arrays. Give the smallest sufficient cookie to the least greedy child. This wastes the least resources. ```typescript function findContentChildren(g: number[], s: number[]): number { g.sort((a, b) => a - b); s.sort((a, b) => a - b); let child = 0; let cookie = 0; while (child < g.length && cookie < s.length) { if (s[cookie] >= g[child]) { child++; } cookie++; } return child; } ``` **Walkthrough** with `g = [1, 2, 3], s = [1, 1]`: ``` Sorted: g = [1, 2, 3], s = [1, 1] cookie=0, child=0: s[0]=1 >= g[0]=1 → child satisfied, child=1 cookie=1, child=1: s[1]=1 < g[1]=2 → cookie too small, skip cookie=2 → out of cookies Answer: 1 child content ``` **Why this works**: Giving a large cookie to a child with a small appetite wastes potential. The exchange argument: if we gave a bigger cookie to a less greedy child, swapping wouldn't help — the greedier child still wouldn't be satisfied by the small cookie. | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(1) | --- ### Queue Reconstruction by Height (LeetCode 406) **Problem**: People are described as `[height, k]` where `k` is the number of people in front who are taller or equal. Reconstruct the queue. **The Greedy Insight**: Sort people by **height descending** (tallest first), then by **k ascending** (fewer people in front first). Then insert each person at index `k`. When you insert a shorter person, they don't affect the `k` values of taller people already placed. ```typescript function reconstructQueue(people: number[][]): number[][] { people.sort((a, b) => { if (a[0] !== b[0]) return b[0] - a[0]; return a[1] - b[1]; }); const queue: number[][] = []; for (const person of people) { queue.splice(person[1], 0, person); } return queue; } ``` **Walkthrough** with `[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]`: ``` Sorted: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]] Insert [7,0] at index 0: [[7,0]] Insert [7,1] at index 1: [[7,0],[7,1]] Insert [6,1] at index 1: [[7,0],[6,1],[7,1]] Insert [5,0] at index 0: [[5,0],[7,0],[6,1],[7,1]] Insert [5,2] at index 2: [[5,0],[7,0],[5,2],[6,1],[7,1]] Insert [4,4] at index 4: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] ``` > The insight: when placing shorter people, they're "invisible" to taller people already in the queue. So taller people's `k` values remain correct regardless of where shorter people are inserted. | Metric | Complexity | |--------|-----------| | Time | O(n²) | | Space | O(n) | --- ## Pattern 4: Two Pointers Greedy Some greedy problems use two pointers — usually one at each end of a sorted array — to make optimal choices from both directions. --- ### Container With Most Water (LeetCode 11) **Problem**: Given heights of vertical lines at each position, find two lines that form a container holding the most water. **The Greedy Insight**: Start with the widest container (pointers at both ends). The water is limited by the shorter line. Move the shorter pointer inward — moving the taller one can never increase the area (width decreases and height is still bounded by the shorter side). ```typescript function maxArea(height: number[]): number { let left = 0; let right = height.length - 1; let max = 0; while (left < right) { const width = right - left; const h = Math.min(height[left], height[right]); max = Math.max(max, width * h); if (height[left] < height[right]) { left++; } else { right--; } } return max; } ``` **Why moving the shorter pointer works**: The area is `min(left, right) × width`. If we move the *taller* pointer, width decreases and the min height can only stay the same or decrease — area can't improve. If we move the *shorter* pointer, width decreases but the min height *might* increase enough to compensate. So moving the shorter pointer is the only choice that has a chance of finding a better answer. > This is the exchange argument in action: any other strategy (like moving the taller pointer) is provably no better. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### Gas Station (LeetCode 134) **Problem**: There are `n` gas stations in a circle. `gas[i]` is the gas available at station `i`, and `cost[i]` is the gas needed to travel to the next station. Find the starting station index to complete the circuit, or return -1 if impossible. **The Greedy Insight**: Two key observations: 1. If `totalGas >= totalCost`, a solution is guaranteed to exist. 2. If starting from station `s`, your tank drops below 0 at station `j`, then **no station between s and j** can be the answer (they'd run out even sooner since they'd start with less accumulated gas). So jump the start to `j + 1`. This is Kadane's algorithm in disguise — find the starting point of the maximum subarray (the gas surplus). ```typescript function canCompleteCircuit(gas: number[], cost: number[]): number { let totalSurplus = 0; let currentSurplus = 0; let start = 0; for (let i = 0; i < gas.length; i++) { const diff = gas[i] - cost[i]; totalSurplus += diff; currentSurplus += diff; if (currentSurplus < 0) { start = i + 1; currentSurplus = 0; } } return totalSurplus >= 0 ? start : -1; } ``` **Walkthrough** with `gas = [1,2,3,4,5], cost = [3,4,5,1,2]`: ``` i=0: diff = 1-3 = -2, totalSurplus = -2, currentSurplus = -2 < 0 → start=1, reset i=1: diff = 2-4 = -2, totalSurplus = -4, currentSurplus = -2 < 0 → start=2, reset i=2: diff = 3-5 = -2, totalSurplus = -6, currentSurplus = -2 < 0 → start=3, reset i=3: diff = 4-1 = 3, totalSurplus = -3, currentSurplus = 3 i=4: diff = 5-2 = 3, totalSurplus = 0, currentSurplus = 6 totalSurplus(0) >= 0 → return start = 3 ``` > The proof: if `totalSurplus >= 0`, there's enough gas overall. The point where `currentSurplus` is most negative is the worst starting point. By resetting at every dip below zero, we find the complementary starting point — the one that avoids all the bad stretches. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) | --- ### Boats to Save People (LeetCode 881) **Problem**: People with given weights need boats. Each boat can carry at most 2 people and has a weight limit. Find the minimum number of boats. **The Greedy Insight**: Sort by weight. Try to pair the heaviest person with the lightest. If they fit together, great — pair them. If not, the heaviest person takes a boat alone (they can't pair with anyone lighter either). ```typescript function numRescueBoats(people: number[], limit: number): number { people.sort((a, b) => a - b); let left = 0; let right = people.length - 1; let boats = 0; while (left <= right) { if (people[left] + people[right] <= limit) { left++; } right--; boats++; } return boats; } ``` **Walkthrough** with `people = [3, 2, 2, 1], limit = 3`: ``` Sorted: [1, 2, 2, 3] left=0, right=3: 1+3=4 > 3 → heavy alone, right--, boats=1 left=0, right=2: 1+2=3 <= 3 → pair! left++, right--, boats=2 left=1, right=1: 2+2=4 > 3 → alone, right--, boats=3 Answer: 3 boats ``` **Exchange argument**: If we paired two light people instead of pairing light+heavy, the heavy person still needs their own boat. We'd use at least as many boats, never fewer. So pairing extremes is optimal. | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(1) | --- ## Pattern 5: Digit / String Greedy These problems manipulate digits or characters, using greedy logic (often with a stack) to build the optimal result character by character. --- ### Remove K Digits (LeetCode 402) **Problem**: Given a non-negative integer as a string and integer `k`, remove `k` digits to make the number as small as possible. **The Greedy Insight**: Scan left to right. Whenever a digit is smaller than the one before it, removing the previous (larger) digit makes the number smaller. This is a **monotonic stack** pattern — maintain a non-decreasing sequence of digits. ```typescript function removeKdigits(num: string, k: number): string { const stack: string[] = []; for (const digit of num) { while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) { stack.pop(); k--; } stack.push(digit); } // If k > 0, remove from the end (stack is non-decreasing) while (k > 0) { stack.pop(); k--; } // Remove leading zeros const result = stack.join('').replace(/^0+/, ''); return result || '0'; } ``` **Walkthrough** with `num = "1432219", k = 3`: ``` '1': stack = [1] '4': 4 > 1, push → [1, 4] '3': 3 < 4, pop 4 (k=2) → [1], 3 > 1, push → [1, 3] '2': 2 < 3, pop 3 (k=1) → [1], 2 > 1, push → [1, 2] '2': 2 >= 2, push → [1, 2, 2] '1': 1 < 2, pop 2 (k=0) → [1, 2], push 1 → [1, 2, 1] '9': push → [1, 2, 1, 9] Result: "1219" ``` > The monotonic stack ensures we always remove the leftmost "peak" — a digit that's larger than what follows. Since leftmost digits have the highest place value, removing a peak there has the maximum impact on reducing the number. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(n) | --- ### Largest Number (LeetCode 179) **Problem**: Given a list of non-negative integers, arrange them to form the largest possible number. **The Greedy Insight**: Custom comparator. For two numbers `a` and `b`, compare the concatenations `a+b` vs `b+a`. If `"930"` > `"309"`, then `9` should come before `30`. ```typescript function largestNumber(nums: number[]): string { const strs = nums.map(String); strs.sort((a, b) => { const ab = a + b; const ba = b + a; return ba.localeCompare(ab); }); if (strs[0] === '0') return '0'; return strs.join(''); } ``` **Why `a+b` vs `b+a` works**: This defines a **total ordering** on the strings. If `ab > ba`, then `a` should come first. This ordering is transitive (provable), so sorting by it gives the globally optimal arrangement. **Example** with `[3, 30, 34, 5, 9]`: ``` Comparisons: "9" + "5" = "95" vs "5" + "9" = "59" → "9" first "5" + "34" = "534" vs "34" + "5" = "345" → "5" first "34" + "3" = "343" vs "3" + "34" = "334" → "34" first "30" + "3" = "303" vs "3" + "30" = "330" → "3" first Sorted: ["9", "5", "34", "3", "30"] Result: "9534330" ``` | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(n) | --- ### Partition Labels (LeetCode 763) **Problem**: Given a string, partition it into as many parts as possible so that each letter appears in at most one part. Return the sizes. **The Greedy Insight**: For each character, find its **last occurrence**. As you scan left to right, maintain the farthest last occurrence of any character in the current partition. When your position reaches that farthest point, you've found a partition boundary. ```typescript function partitionLabels(s: string): number[] { const lastIndex: Map = new Map(); for (let i = 0; i < s.length; i++) { lastIndex.set(s[i], i); } const result: number[] = []; let start = 0; let end = 0; for (let i = 0; i < s.length; i++) { end = Math.max(end, lastIndex.get(s[i])!); if (i === end) { result.push(end - start + 1); start = i + 1; } } return result; } ``` **Walkthrough** with `s = "ababcbacadefegdehijhklij"`: ``` Last occurrences: a→8, b→5, c→7, d→14, e→15, f→11, g→13, h→19, i→22, j→23, k→20, l→21 i=0 'a': end = max(0, 8) = 8 i=1 'b': end = max(8, 5) = 8 ... i=8 'a': end = max(8, 8) = 8 → i === end → partition! size = 9 i=9 'd': end = max(9, 14) = 14 ... i=15 'e': end = max(15, 15) = 15 → i === end → partition! size = 7 i=16 'h': end = max(16, 19) = 19 ... i=23 'j': end = max(23, 23) = 23 → i === end → partition! size = 8 Result: [9, 7, 8] ``` > The greedy choice: extend the current partition to include all characters' last occurrences. Cut as soon as you can. This guarantees maximum number of partitions because each one is as small as possible. | Metric | Complexity | |--------|-----------| | Time | O(n) | | Space | O(1) (26 letters max) | --- ## Pattern 6: Huffman-Style / Priority Queue Greedy Some problems require always processing the smallest (or largest) element first. A **priority queue (heap)** is the natural data structure for these greedy strategies. --- ### Minimum Cost to Connect Sticks **Problem**: You have sticks of various lengths. To connect two sticks, the cost is the sum of their lengths. Find the minimum total cost to connect all sticks into one. **The Greedy Insight**: Always merge the two shortest sticks first. This minimizes the cost at each step because shorter sticks contribute to fewer future merges. This is exactly the strategy behind **Huffman coding**. ```typescript function connectSticks(sticks: number[]): number { if (sticks.length <= 1) return 0; // Min-heap simulation const heap = [...sticks].sort((a, b) => a - b); const push = (val: number) => { heap.push(val); heap.sort((a, b) => a - b); }; const pop = () => heap.shift()!; let totalCost = 0; while (heap.length > 1) { const first = pop(); const second = pop(); const cost = first + second; totalCost += cost; push(cost); } return totalCost; } ``` **Walkthrough** with `sticks = [2, 4, 3]`: ``` Heap: [2, 3, 4] Merge 2+3 = 5, cost = 5. Heap: [4, 5] Merge 4+5 = 9, cost = 9. Heap: [9] Total cost: 5 + 9 = 14 ``` Compare with merging 3+4 first: cost 7, then 2+7 = 9 → total 16. Or 2+4 first: cost 6, then 3+6 = 9 → total 15. Merging the two smallest first (2+3) gives the minimum total cost of 14. > **Why it works**: Sticks merged earlier appear in more subsequent merges. By merging the smallest first, the "expensive" big sticks are involved in fewer total merges. | Metric | Complexity | |--------|-----------| | Time | O(n log n) | | Space | O(n) | --- ### Reorganize String (LeetCode 767) **Problem**: Given a string, rearrange it so that no two adjacent characters are the same. Return any valid rearrangement or empty string if impossible. **The Greedy Insight**: Always place the most frequent character next. Use a max-heap to always pick the highest-frequency character that isn't the same as the one just placed. ```typescript function reorganizeString(s: string): string { const freq: Map = new Map(); for (const c of s) { freq.set(c, (freq.get(c) || 0) + 1); } // Check impossibility: if any char appears more than ⌈n/2⌉ times const maxAllowed = Math.ceil(s.length / 2); for (const count of freq.values()) { if (count > maxAllowed) return ''; } // Build sorted array of [char, freq] pairs (simulate max-heap) const entries = [...freq.entries()].sort((a, b) => b[1] - a[1]); const result: string[] = []; // Place most frequent characters in even indices first, then odd let idx = 0; const arr = new Array(s.length); for (const [char, count] of entries) { for (let i = 0; i < count; i++) { if (idx >= s.length) idx = 1; arr[idx] = char; idx += 2; } } return arr.join(''); } ``` **Alternative approach with explicit heap logic**: ```typescript function reorganizeStringHeap(s: string): string { const freq: Map = new Map(); for (const c of s) { freq.set(c, (freq.get(c) || 0) + 1); } // Sort by frequency descending (simulates max-heap extraction) const sorted = [...freq.entries()].sort((a, b) => b[1] - a[1]); if (sorted[0][1] > Math.ceil(s.length / 2)) return ''; const result: string[] = []; let prev: [string, number] | null = null; // Greedy: always pick the most frequent that isn't the previous while (sorted.length > 0 || prev !== null) { if (sorted.length === 0 && prev !== null) return ''; sorted.sort((a, b) => b[1] - a[1]); const [char, count] = sorted.shift()!; result.push(char); if (prev !== null && prev[1] > 0) { sorted.push(prev); } prev = count - 1 > 0 ? [char, count - 1] : null; } return result.join(''); } ``` > The first approach (fill even indices, then odd) is simpler and faster for interviews. The heap approach is conceptually cleaner and more generalizable. | Metric | Complexity | |--------|-----------| | Time | O(n log k) where k = unique chars | | Space | O(n) | --- ## Greedy vs Dynamic Programming: The Decision Framework This is the question that haunts every interview: **"Should I use greedy or DP?"** Here's your framework. ### The Core Question > **Can you prove that making the locally optimal choice at each step leads to the globally optimal solution?** If **yes** → Greedy. If **no** (or you're not sure) → DP. ### The Exchange Argument (Informal) Imagine you have an optimal solution. Now imagine swapping one of its choices with the greedy choice. If the result is **at least as good**, the greedy approach is safe. If swapping could make things worse, you might need DP. ### The Comparison Table | Property | Greedy | Dynamic Programming | |----------|--------|-------------------| | Makes choices | One at a time, never revisits | Considers all options, picks best | | Proof needed | Greedy choice property | Optimal substructure + overlapping subproblems | | Time complexity | Usually O(n log n) or O(n) | Usually O(n²) or O(n × m) | | Space complexity | Usually O(1) or O(n) | Usually O(n) or O(n × m) | | Implementation | Simple iteration | Recursion + memo or table | | When it fails | Locally optimal ≠ globally optimal | N/A (always finds optimal if correct) | ### Problems That LOOK Greedy But Need DP | Problem | Why Greedy Fails | Why DP Works | |---------|-----------------|-------------| | Coin Change (arbitrary) | Biggest-first skips combos | Try all denominations at each amount | | 0/1 Knapsack | Heaviest value/weight ratio fails | Consider include/exclude for each item | | Longest Increasing Subsequence | Greedy picks next smallest, misses longer paths | Track best ending at each length | | Edit Distance | No clear local choice | Min of insert/delete/replace at each position | | Word Break | Matching longest prefix fails | Try all valid prefixes at each position | ### Problems That ARE Greedy | Problem | Why Greedy Works | |---------|-----------------| | Activity Selection | Earliest ending ≤ any other choice (exchange argument) | | Huffman Coding | Merging smallest always optimal (exchange argument) | | Fractional Knapsack | Best ratio first, can take fractions | | Jump Game | Farthest reachable only grows | | Gas Station | If total gas ≥ total cost, a valid start exists | ### The Decision Flowchart ``` Is there an obvious "best local choice" at each step? ├── No → Try DP ├── Yes → Can you prove it's always safe? ├── No → Try DP (or test with counterexample) └── Yes → Greedy! └── Does the problem have overlapping subproblems? ├── Yes → DP might still be needed └── No → Greedy is confirmed ``` > **Rule of thumb**: If you can construct a small counterexample where greedy fails, it's not a greedy problem. Try denominations [1, 3, 4] making 6, or a knapsack where the best ratio item blocks better combinations. --- ## How to Prove Greedy Works You won't write formal proofs in interviews, but you should be able to sketch *why* your greedy choice is safe. Here are the three standard techniques, explained intuitively. ### 1. Exchange Argument **Idea**: Take any optimal solution. Show that you can "swap" one of its choices for the greedy choice without making things worse. **Example** (Activity Selection): Suppose an optimal solution picks activity X first, but greedy picks activity G (which ends earlier). Since G ends no later than X, everything that was compatible with X is also compatible with G. So swapping X for G gives a solution that's at least as good. > "If I swap any choice for the greedy choice, things don't get worse. Therefore, a solution using the greedy choice exists among the optimal solutions." ### 2. Greedy Stays Ahead **Idea**: Show by induction that after each step, the greedy solution is at least as good as any other solution at that step. **Example** (Jump Game II): After k jumps, the greedy algorithm reaches at least as far as any other strategy with k jumps. Since it's always "ahead," it finishes in the fewest jumps. ### 3. Contradiction **Idea**: Assume greedy doesn't give the optimal answer. Derive a contradiction. **Example** (Gas Station): Assume the greedy starting point fails. Then total gas < total cost for the circuit starting there. But we know total gas ≥ total cost overall. The only starting point that avoids all deficit stretches is the greedy one — contradiction. --- ## Common Pitfalls Even when greedy is the right approach, it's easy to get tripped up. Here are the mistakes I see most often: ### 1. Assuming Greedy Works Without Verification The most dangerous pitfall. Your solution *looks* right, passes the examples, and then fails on a tricky test case. Always ask: "Can I construct a counterexample where greedy fails?" If you can't after trying 2-3 examples, you're probably safe. ### 2. Wrong Sorting Criteria Interval problems are especially sensitive to this. Sorting by start time vs end time vs length can give completely different results. **Non-overlapping intervals**: sort by **end time**. **Merge intervals**: sort by **start time**. Getting this wrong gives a solution that's subtly broken. ### 3. Not Handling Ties When two elements have equal priority, the tiebreaker matters. In Queue Reconstruction by Height, equal heights must be sorted by `k` ascending. In many interval problems, equal start or end times need specific handling. Always think about ties. ### 4. Edge Cases - **Empty input**: Return 0, empty array, or appropriate default - **Single element**: Usually the answer is trivial - **All same values**: Does your logic degenerate? - **Already sorted input**: Does your algorithm handle this correctly? - **Maximum constraint values**: Does your solution TLE? ### 5. Off-by-One Errors in Intervals The eternal question: is `[1,2]` and `[2,3]` overlapping or not? Read the problem carefully. Some problems treat touching endpoints as overlapping, others don't. In **Non-overlapping Intervals**, `[1,2]` and `[2,3]` are NOT overlapping. In **Minimum Arrows**, a balloon at `[1,2]` IS burst by an arrow at `x=2`. --- ## Cheat Sheet ### Pattern → Problem Mapping | Pattern | Problems | Key Sorting | |---------|----------|-------------| | Interval Scheduling | 435, 56, 57, 253, 452 | By end time or start time | | Jump / Reachability | 55, 45, 1024 | No sort needed (array order) | | Scheduling / Assignment | 621, 455, 406 | By frequency, size, or height | | Two Pointers Greedy | 11, 134, 881 | By weight or no sort needed | | Digit / String Greedy | 402, 179, 763 | Custom comparators | | Priority Queue Greedy | Connect Sticks, 767 | By frequency (heap) | ### Sorting Strategy Quick Reference | When You Want To... | Sort By... | |---------------------|------------| | Maximize non-overlapping intervals | End time ascending | | Merge overlapping intervals | Start time ascending | | Minimize rooms/resources | Start time + min-heap of ends | | Pair smallest with largest | Value ascending, two pointers | | Build smallest number | Monotonic stack (non-decreasing) | | Build largest number | Custom comparator (a+b vs b+a) | | Assign resources to requirements | Both ascending, match greedily | | Insert by relative position | Descending value, insert at position | ### Greedy vs DP Decision Tree ``` Question: Can I solve this greedily? Step 1: Is there a natural "best local choice"? → No: Almost certainly DP (or backtracking) → Yes: Continue to Step 2 Step 2: Try a counterexample with 3-5 elements. → Greedy fails: Use DP → Greedy works: Continue to Step 3 Step 3: Can you sketch an exchange argument? "If I swap the greedy choice for any other, does it get worse?" → No (swapping doesn't help): Greedy is correct → Yes (swapping could help): Use DP ``` ### Big O Reference | Problem | Time | Space | |---------|------|-------| | Non-overlapping Intervals | O(n log n) | O(1) | | Merge Intervals | O(n log n) | O(n) | | Insert Interval | O(n) | O(n) | | Meeting Rooms II | O(n log n) | O(n) | | Min Arrows Balloons | O(n log n) | O(1) | | Jump Game | O(n) | O(1) | | Jump Game II | O(n) | O(1) | | Video Stitching | O(n log n) | O(1) | | Task Scheduler | O(n) | O(1) | | Assign Cookies | O(n log n) | O(1) | | Queue Reconstruction | O(n²) | O(n) | | Container With Most Water | O(n) | O(1) | | Gas Station | O(n) | O(1) | | Boats to Save People | O(n log n) | O(1) | | Remove K Digits | O(n) | O(n) | | Largest Number | O(n log n) | O(n) | | Partition Labels | O(n) | O(1) | | Connect Sticks | O(n log n) | O(n) | | Reorganize String | O(n log k) | O(n) | --- ## What's Next You now have a comprehensive toolkit for greedy algorithms. You understand the greedy choice property, optimal substructure, and the framework for deciding whether greedy applies. You've seen six major patterns — intervals, jumps, scheduling, two-pointer, string/digit, and priority queue greedy — and solved 19 problems across those patterns. You know how to prove greedy works, how to spot when it doesn't, and how to pivot to DP when needed. But the journey doesn't end here. Greedy connects to several deeper topics: - **Dynamic Programming** — When greedy fails, DP is your safety net. Many problems that *look* greedy require DP because the locally optimal choice isn't globally optimal. Coin change, knapsack, and longest increasing subsequence all share this trait. - **Graph Algorithms** — Greedy is the foundation of Dijkstra's algorithm (shortest path), Kruskal's and Prim's algorithms (minimum spanning tree), and topological sorting with Kahn's algorithm. These are greedy on graphs. - **Binary Search** — Sometimes the "greedy choice" is about finding the right threshold. Binary search on the answer combined with a greedy feasibility check is a powerful technique for optimization problems. - **Backtracking** — When you can't prove the greedy choice is safe, backtracking lets you explore all options. Greedy is essentially backtracking where you never need to "back" — you commit to each choice with confidence. Each of these topics gets its own "Made Simple" article. The patterns stack on each other, and the greedy intuition you built here — always asking "is the local choice globally safe?" — applies to every optimization problem you'll encounter. > "Greedy is the art of confident commitment — making each choice without regret, because you've proven that looking back would never help." Keep practicing. Start with the interval problems (they're the most common in interviews), then tackle the jump games, then the string manipulation problems. Before long, you'll see a problem and your brain will instantly ask: "Can I sort this and sweep through greedily?" And more often than you'd expect, the answer will be yes. --- ## Thanks for Reading! If this guide helped greedy algorithms click for you, share it with a friend who's stuck on those interval scheduling problems. The best way to solidify your understanding is to explain it to someone else — especially that tricky "why sort by end time?" argument. Keep building. Keep solving. You've got this. **Your Dev Brain, Now Thinking Greedily** ---

Problem Solving Patterns: Greedy Algorithms, Made Simple