Greedy Algorithm Pattern

Overview

Make locally optimal choices at each step hoping to find a global optimum. Works when local choices don't compromise future options (greedy-choice property) and optimal substructure exists.

When to Use

• Interval scheduling/selection
• Huffman coding
• Minimum spanning tree
• Activity selection
• Task scheduling
• Coin change (specific denominations)
• String reconstruction

Template Code

Interval Scheduling (Max Non-overlapping)

public int maxNonOverlapping(int[][] intervals) {
    // Sort by end time (greedy: finish earliest)
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int count = 0;
    int lastEnd = Integer.MIN_VALUE;

    for (int[] interval : intervals) {
        if (interval[0] >= lastEnd) {
            count++;
            lastEnd = interval[1];
        }
    }

    return count;
}

Jump Game

public boolean canJump(int[] nums) {
    int maxReach = 0;

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

    return true;
}

Jump Game II (Minimum Jumps)

public int jump(int[] nums) {
    int jumps = 0;
    int currentEnd = 0;
    int farthest = 0;

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);

        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }

    return jumps;
}

Gas Station

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalGas = 0, totalCost = 0;
    int tank = 0, start = 0;

    for (int i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        tank += gas[i] - cost[i];

        if (tank < 0) {
            // Can't reach i+1 from current start
            start = i + 1;
            tank = 0;
        }
    }

    return totalGas >= totalCost ? start : -1;
}

Best Time to Buy and Sell Stock II

public int maxProfit(int[] prices) {
    int profit = 0;

    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }

    return profit;
}

Partition Labels

public List<Integer> partitionLabels(String s) {
    int[] lastIndex = new int[26];

    // Find last occurrence of each character
    for (int i = 0; i < s.length(); i++) {
        lastIndex[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, lastIndex[s.charAt(i) - 'a']);

        if (i == end) {
            result.add(end - start + 1);
            start = i + 1;
        }
    }

    return result;
}

Task Scheduler

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    int maxFreq = 0;
    int maxCount = 0;

    for (char task : tasks) {
        freq[task - 'A']++;
        if (freq[task - 'A'] > maxFreq) {
            maxFreq = freq[task - 'A'];
            maxCount = 1;
        } else if (freq[task - 'A'] == maxFreq) {
            maxCount++;
        }
    }

    // (maxFreq - 1) complete cycles + last partial cycle
    int intervals = (maxFreq - 1) * (n + 1) + maxCount;

    return Math.max(intervals, tasks.length);
}

Candy Distribution

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);

    // Left to right: if higher rating than left, give more
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // Right to left: if higher rating than right, give more
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    int total = 0;
    for (int c : candies) {
        total += c;
    }
    return total;
}

Minimum Platforms (Train Schedule)

public int findPlatform(int[] arrivals, int[] departures) {
    Arrays.sort(arrivals);
    Arrays.sort(departures);

    int platforms = 0, maxPlatforms = 0;
    int i = 0, j = 0;

    while (i < arrivals.length && j < departures.length) {
        if (arrivals[i] <= departures[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        maxPlatforms = Math.max(maxPlatforms, platforms);
    }

    return maxPlatforms;
}

Assign Cookies

public int findContentChildren(int[] greed, int[] cookies) {
    Arrays.sort(greed);
    Arrays.sort(cookies);

    int child = 0, cookie = 0;

    while (child < greed.length && cookie < cookies.length) {
        if (cookies[cookie] >= greed[child]) {
            child++;
        }
        cookie++;
    }

    return child;
}

Boats to Save People

public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int boats = 0;
    int left = 0, right = people.length - 1;

    while (left <= right) {
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--;
        boats++;
    }

    return boats;
}

Fractional Knapsack

public double fractionalKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    double[][] items = new double[n][2];

    for (int i = 0; i < n; i++) {
        items[i][0] = weights[i];
        items[i][1] = (double) values[i] / weights[i];  // Value per unit
    }

    // Sort by value per unit (descending)
    Arrays.sort(items, (a, b) -> Double.compare(b[1], a[1]));

    double totalValue = 0;
    double remainingCapacity = capacity;

    for (double[] item : items) {
        if (remainingCapacity >= item[0]) {
            // Take whole item
            totalValue += item[0] * item[1];
            remainingCapacity -= item[0];
        } else {
            // Take fraction
            totalValue += remainingCapacity * item[1];
            break;
        }
    }

    return totalValue;
}

Reorganize String

public String reorganizeString(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) {
        freq[c - 'a']++;
    }

    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            maxHeap.offer(new int[]{i, freq[i]});
        }
    }

    StringBuilder result = new StringBuilder();
    int[] prev = null;

    while (!maxHeap.isEmpty()) {
        int[] curr = maxHeap.poll();
        result.append((char) (curr[0] + 'a'));
        curr[1]--;

        if (prev != null && prev[1] > 0) {
            maxHeap.offer(prev);
        }

        prev = curr;
    }

    return result.length() == s.length() ? result.toString() : "";
}

Time & Space Complexity

Problem	Time	Space
Interval scheduling	O(n log n)	O(1)
Jump game	O(n)	O(1)
Gas station	O(n)	O(1)
Task scheduler	O(n)	O(1)
Candy	O(n)	O(n)

Common Interview Questions

1. Jump Game - Can reach last index?
2. Jump Game II - Min jumps to reach end
3. Gas Station - Starting point for circular trip
4. Best Time to Buy and Sell II - Max profit, multiple transactions
5. Partition Labels - Min partitions, each char in one part
6. Task Scheduler - Min time with cooldown
7. Candy - Min candies with rating constraints
8. Meeting Rooms II - Min rooms needed
9. Non-overlapping Intervals - Min removals
10. Minimum Number of Arrows - Burst balloons
11. Assign Cookies - Max satisfied children
12. Boats to Save People - Min boats needed
13. Reorganize String - No adjacent same chars
14. Queue Reconstruction by Height - Rebuild queue

Tips & Tricks

• Sorting is often the first step (by end time, value/weight, etc.)
• Prove greedy works by showing optimal substructure
• Common greedy strategies:
• Select earliest finish time
• Select smallest/largest first
• Select highest value-to-weight ratio
• Two-pointer often pairs with greedy after sorting
• If greedy fails, consider DP
• Counter-examples help identify when greedy doesn't work