Greedy

Back to DSA & Algorithms/00 - Roadmap Overview

What is Greedy?

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to the globally optimal solution. Unlike DP, greedy never reconsiders past choices.

When Does Greedy Work?

It works when the problem has the greedy choice property: making the best local choice never eliminates the true global optimum.

How to verify: If you can prove that the greedy choice is always part of some optimal solution, it works. In practice, try a few examples and see if greedy gives the right answer.

Greedy vs DP

	Greedy	DP
Decision style	Make best choice now, never revisit	Consider all subproblems
Time	Usually O(n log n) or O(n)	Usually O(n²) or O(n×m)
Correctness	Must prove it works	Always correct if formulated right
Rule of thumb	Try greedy first. If counterexample exists → use DP

The Mental Model

You're hiking and want to reach the highest peak. Greedy says "always walk uphill." This works if there's only one peak (the global maximum). It fails if there are multiple peaks (you might get stuck on a local maximum).

Pattern 1: Interval Scheduling / Selection

What it is

Given intervals, select the maximum number of non-overlapping ones, or find the minimum number to remove.

Key Insight: Sort by END time, then greedily pick.

Why end time? If you pick the interval that ends earliest, you leave the most room for future intervals.

java
// Minimum intervals to remove so the rest don't overlap
public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));  // Sort by END time
    int count = 0;
    int prevEnd = Integer.MIN_VALUE;

    for (int[] interval : intervals) {
        int start = interval[0], end = interval[1];
        if (start >= prevEnd) {
            prevEnd = end;   // Take this interval (no overlap)
        } else {
            count++;         // Skip this interval (overlap)
        }
    }

    return count;
}

// Walkthrough: [[1,2],[2,3],[3,4],[1,3]]
// Sorted by end: [[1,2],[2,3],[1,3],[3,4]]
// [1,2]: 1 >= MIN_VALUE → take. prevEnd=2
// [2,3]: 2 >= 2 → take. prevEnd=3
// [1,3]: 1 < 3 → overlap! Skip. count=1
// [3,4]: 3 >= 3 → take. prevEnd=4
// Answer: 1 (remove [1,3])

Problems

435. Non-overlapping Intervals - Medium
452. Minimum Number of Arrows to Burst Balloons - Medium

Pattern 2: Jump Game

What it is

Track the farthest position you can reach while scanning left to right.

java
// Can you reach the last index?
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;        // Can't reach this position
        }
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

// Minimum jumps to reach the end
public int jump(int[] nums) {
    int jumps = 0;
    int currEnd = 0;     // End of current jump range
    int farthest = 0;    // Farthest we can reach

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currEnd) {     // Must jump now
            jumps++;
            currEnd = farthest;
        }
    }

    return jumps;
}

// Mental model for Jump Game II:
// BFS by levels. Each "level" = one jump.
// currEnd = boundary of current BFS level.
// farthest = boundary of next BFS level.

Gas Station

java
// Circular route with gas stations. Can you complete the circuit?
public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalGas = 0, totalCost = 0;
    for (int i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
    }
    if (totalGas < totalCost) {
        return -1;  // Not enough total gas
    }

    int tank = 0;
    int start = 0;
    for (int i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            start = i + 1;  // Can't start from anywhere before i+1
            tank = 0;
        }
    }

    return start;
}

// Why this works: If total gas >= total cost, a solution exists.
// If starting from `start` causes tank < 0 at some point,
// then no station between `start` and that point works either.
// So we jump to the next station.

Problems

55. Jump Game - Medium
45. Jump Game II - Medium
134. Gas Station - Medium

Pattern 3: Greedy String / Array

java
// Partition Labels: split string so each letter appears in at most one part
public List<Integer> partitionLabels(String s) {
    // For each character, record its LAST occurrence
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;
    }

    List<Integer> result = new ArrayList<>();
    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);  // Extend partition to include last occurrence
        if (i == end) {                                 // Reached the end of current partition
            result.add(end - start + 1);
            start = i + 1;
        }
    }

    return result;
}

// "ababcbacadefegdehijhklij"
// 'a' last at 8, 'b' last at 5, 'c' last at 7...
// Partition extends until i reaches the farthest last-occurrence seen.

Problems

Things You MUST Be Aware Of

1. Sorting is Almost Always Step 1

Most greedy problems require sorting first.
The sort criterion is the key insight:
  - Intervals: sort by end time
  - Tasks: sort by deadline or priority
  - Scheduling: sort by cost difference

2. Proving Greedy Correctness

Exchange argument: show that swapping the greedy choice with any other
doesn't improve the answer (and might make it worse).

If you can't prove it → it's probably wrong → use DP instead.

3. Common Trap: Greedy Looks Right But Isn't

Example: Coin change with denominations [1, 3, 4], target = 6
Greedy: 4 + 1 + 1 = 3 coins
Optimal: 3 + 3 = 2 coins

Greedy fails here! Need DP.
Greedy only works for coin change with specific denominations (like US coins).