Greedy Algorithms

One-line summary: Make the locally optimal choice at each step — works when local optima lead to a global optimum (proved by exchange argument).

---

Diagram

Concept

A greedy algorithm: picks best available option, never backtracks. Works when greedy choice property + optimal substructure hold. When greedy fails, use DP.

Typically requires initial sorting. Time is usually O(n log n).

---

Common Patterns

Interval Scheduling (sort by end time)

function maxNonOverlapping(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0,
    lastEnd = -Infinity;
  for (const [s, e] of intervals)
    if (s >= lastEnd) {
      count++;
      lastEnd = e;
    }
  return count;
}

Jump Game

function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

---

Pitfalls

• Greedy doesn't always work — verify with exchange argument or counterexample
• 0/1 Knapsack fails with greedy — use DP
• Greedy needs correct sorting criterion — wrong sort → wrong answer

---

Practice Problems

Problem	Difficulty	Solution
LC 455 — Assign Cookies	Easy
LC 55 — Jump Game	Medium
LC 45 — Jump Game II	Medium
LC 435 — Non-overlapping Intervals	Medium
LC 134 — Gas Station	Medium
LC 763 — Partition Labels	Medium
LC 406 — Queue Reconstruction by Height	Medium
LC 1005 — Maximize Sum After K Negations	Easy
CC — Good Sequences (CHEFSQ)	Easy
CC — Election Chips (ELECCHRP)	Medium
LC 135 — Candy	Hard
LC 122 — Best Time to Buy and Sell Stock II	Easy
LC 860 — Lemonade Change	Easy
LC 944 — Delete Columns to Make Sorted	Easy
LC 1221 — Split a String in Balanced Strings	Easy
LC 1710 — Maximum Units on a Truck	Easy
LC 11 — Container With Most Water	Medium
LC 56 — Merge Intervals	Medium
LC 452 — Minimum Number of Arrows to Burst Balloons	Medium
LC 621 — Task Scheduler	Medium
LC 714 — Best Time to Buy and Sell Stock with Transaction Fee	Medium
LC 1029 — Two City Scheduling	Medium
LC 1247 — Minimum Swaps to Make Strings Equal	Medium
LC 1481 — Least Number of Unique Integers after K Removals	Medium
LC 1642 — Furthest Building You Can Reach	Medium
LC 1647 — Minimum Deletions to Make Character Frequencies Unique	Medium
LC 1899 — Merge Triplets to Form Target Triplet	Medium
CC — Activity Selection (ACTSEL)	Medium
CC — Fractional Knapsack (FRACKNAP)	Medium
LC 68 — Text Justification	Hard
LC 321 — Create Maximum Number	Hard
LC 330 — Patching Array	Hard
LC 502 — IPO	Hard
LC 630 — Course Schedule III	Hard
LC 757 — Set Intersection Size At Least Two	Hard
LC 765 — Couples Holding Hands	Hard
LC 968 — Binary Tree Cameras	Hard
LC 1665 — Minimum Initial Energy to Finish Tasks	Hard
CC — Job Sequencing (JOBSEQ)	Hard
CC — Advanced Greedy (ADVGREEDY)	Hard

---

Related Topics

• Dynamic Programming — when greedy fails, DP is next
• Sorting — greedy often starts with a sort

← Back to Home · © sparshjaswal