All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›Greedy Algorithms

Greedy Algorithms

0/12 in this phase0/57 across the roadmap

📖 Concept

Greedy algorithms make the locally optimal choice at each step, hoping to reach the globally optimal solution. They don't reconsider past choices — no backtracking.

When greedy works:

  • The problem has optimal substructure (optimal solution contains optimal sub-solutions)
  • The problem has the greedy choice property (local optimal → global optimal)
  • You can PROVE that greedy gives the optimal answer (not just "seems right")

When greedy DOESN'T work:

  • Coin change with arbitrary denominations (greedy fails: coins [1,3,4], target 6 → greedy gives 4+1+1=3 coins, optimal is 3+3=2 coins)
  • Most optimization problems need DP, not greedy

Classic greedy problems:

  1. Activity selection — Pick max non-overlapping intervals
  2. Fractional knapsack — Take items by value/weight ratio
  3. Huffman coding — Build optimal prefix code
  4. Jump game — Can you reach the last index?
  5. Gas station — Find starting station for circular route

Proving greedy correctness:

  1. Exchange argument — Show that swapping any non-greedy choice with the greedy choice doesn't worsen the solution
  2. Stays ahead — Show the greedy solution is always at least as good as any other solution at each step

🏠 Real-world analogy: Always taking the next exit on a highway that gets you closest to your destination. It works for highway navigation (greedy is optimal) but fails for a maze (need backtracking/DP).

💻 Code Example

codeTap to expand ⛶
1// JUMP GAME — Can you reach the last index?
2function canJump(nums: number[]): boolean {
3  let maxReach = 0;
4  for (let i = 0; i < nums.length; i++) {
5    if (i > maxReach) return false; // Can't reach this index
6    maxReach = Math.max(maxReach, i + nums[i]);
7  }
8  return true;
9}
10

11// JUMP GAME II — Minimum jumps to reach end
12function jump(nums: number[]): number {
13  let jumps = 0, currentEnd = 0, farthest = 0;
14  for (let i = 0; i < nums.length - 1; i++) {
15    farthest = Math.max(farthest, i + nums[i]);
16    if (i === currentEnd) {
17      jumps++;
18      currentEnd = farthest;
19    }
20  }
21  return jumps;
22}
23

24// ACTIVITY SELECTION — Max non-overlapping intervals
25function maxActivities(activities: [number, number][]): number {
26  activities.sort((a, b) => a[1] - b[1]); // Sort by END time
27  let count = 1, lastEnd = activities[0][1];
28  for (let i = 1; i < activities.length; i++) {
29    if (activities[i][0] >= lastEnd) {
30      count++;
31      lastEnd = activities[i][1];
32    }
33  }
34  return count;
35}
36

37// MINIMUM PLATFORMS — Trains at a station
38function minPlatforms(arrivals: number[], departures: number[]): number {
39  arrivals.sort((a, b) => a - b);
40  departures.sort((a, b) => a - b);
41  let platforms = 0, maxPlatforms = 0;
42  let i = 0, j = 0;
43  while (i < arrivals.length) {
44    if (arrivals[i] <= departures[j]) {
45      platforms++;
46      maxPlatforms = Math.max(maxPlatforms, platforms);
47      i++;
48    } else {
49      platforms--;
50      j++;
51    }
52  }
53  return maxPlatforms;
54}
55

56// FRACTIONAL KNAPSACK — Greedy by value/weight ratio
57function fractionalKnapsack(
58  items: {weight: number, value: number}[],
59  capacity: number
60): number {
61  items.sort((a, b) => b.value/b.weight - a.value/a.weight);
62  let totalValue = 0;
63  for (const item of items) {
64    if (capacity >= item.weight) {
65      totalValue += item.value;
66      capacity -= item.weight;
67    } else {
68      totalValue += (capacity / item.weight) * item.value;
69      break;
70    }
71  }
72  return totalValue;
73}
74

75// ASSIGN COOKIES — Sort and greedily match
76function findContentChildren(greed: number[], cookies: number[]): number {
77  greed.sort((a, b) => a - b);
78  cookies.sort((a, b) => a - b);
79  let child = 0, cookie = 0;
80  while (child < greed.length && cookie < cookies.length) {
81    if (cookies[cookie] >= greed[child]) child++;
82    cookie++;
83  }
84  return child;
85}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Assign cookies to children (each child has a greed factor)
  2. Jump game — can you reach the last index?
  3. Jump game II — minimum number of jumps
  4. Best time to buy and sell stock II (multiple transactions)
  5. Activity selection / non-overlapping intervals (max count)
  6. Minimum number of meeting rooms (interval scheduling)
  7. Gas station — find starting index for circular trip
  8. Partition labels — partition string so each letter appears in one part
  9. Minimum number of arrows to burst balloons
  10. Task scheduler — schedule tasks with cooldown

⚠️ Common Mistakes

  • Assuming greedy always works — it DOESN'T for many optimization problems (knapsack 0/1, coin change with arbitrary coins)

  • Not sorting first — most greedy algorithms require sorting by some criteria

  • Not proving correctness — greedy can give wrong answers; always verify with counterexamples

  • Confusing greedy with DP — if you need to consider future states, it's not greedy

  • Choosing the wrong greedy criterion — e.g., sorting intervals by start time instead of end time

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Greedy Algorithms

← PreviousBacktracking — Permutations, Combinations, SubsetsNext →Dynamic Programming — Introduction & Thinking