Greedy

Make the locally optimal choice at each step to achieve a globally optimal solution.

8 problems 0 Easy 7 Medium 1 Hard

Overview

Greedy algorithms work when a locally optimal choice leads to a globally optimal solution. They are typically O(n log n) due to sorting, and proving correctness often requires an exchange argument.

When to Use

Jump game
Gas station
Meeting rooms
Task scheduler
Assign cookies
Minimum number of platforms

Common Mistakes

Applying greedy when it does not guarantee optimality
Forgetting to sort the input
Not proving the greedy choice property

Complexity

Time

O(n log n) — dominated by sorting

Space

O(1)

// Jump Game II — greedy
function jump(nums) {
  let jumps = 0, currentEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

Problems (8)

Hide completed

Problem	Difficulty	Companies	Freq	Link
Jump Game	Medium	AmazonMicrosoft +1	High
Jump Game II	Medium	AmazonGoogle +1	High
Gas Station	Medium	AmazonUber +1	Medium
Non-overlapping Intervals	Medium	GoogleFacebook	High
Meeting Rooms II ★	Medium	FacebookAmazon +4	High	★
Queue Reconstruction by Height	Medium	GoogleFacebook	Medium
Minimum Number of Arrows to Burst Balloons	Medium	MicrosoftAmazon	Medium
Candy	Hard	AmazonGoogle	Medium

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee