Mar 10, 2025

Greedy Algorithms

Overview

A greedy algorithm commits to the locally best choice without revisiting earlier decisions. It is correct only when an optimal solution can be transformed to include that choice—often shown with an exchange argument—or when the choice preserves all necessary future possibilities.

Common signals include maximizing reach, choosing the earliest finishing interval, taking the cheapest available action, or maintaining the best boundary seen so far. Greedy solutions are usually short; proving why discarded alternatives cannot help is the real work.

Problems

45. Jump Game II

Find the minimum jumps required to reach the end. Scan the range reachable with the current number of jumps while recording the farthest next reach. Crossing the current range boundary commits one jump and opens the next range, like BFS levels without a queue.

class Solution {
    public int jump(int[] nums) {
        int N = nums.length;
        int l = 0, r = 0;
        int farthest = 0;
        int step = 0;

        while (l <= r) {
            if (farthest >= N - 1) {
                return step;
            }

            for (int i = l; i <= r; i++) {
                farthest = Math.max(farthest, nums[i] + i);
            }
            l = 1 + r;
            r = farthest;
            step++;
        }

        return -1;
    }
}

from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        N = len(nums)
        l, r = 0, 0
        farthest = 0
        step = 0

        while l <= r:
            if farthest >= N-1:
                return step

            for i in range(l, 1 + r):
                farthest = max(farthest, nums[i] + i)
            l = 1 + r
            r = farthest
            step += 1

        return -1

122. Best Time to Buy and Sell Stock II

With unlimited transactions, every positive day-to-day increase can be collected. Adding these local gains produces the same profit as buying at each valley and selling at the following peak, without needing to identify either explicitly.

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

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

        return profit;
    }
}

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(1, len(prices)):
            profit += max(prices[i] - prices[i-1], 0)

        return profit

134. Gas Station

Find a station from which a full circuit is possible. If total gas is smaller than total cost, no solution exists. During the scan, when the running tank becomes negative, none of the stations in that failed segment can be a valid start, so restart after it.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
        }
        if (totalGas < totalCost) {
            return -1;
        }

        int tank = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            tank = tank + gas[i] - cost[i];
            if (tank < 0) {
                tank = 0;
                start = i + 1;
            }
        }

        return start;
    }
}

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        tank = 0
        start = 0

        for i in range(len(gas)):
            tank = tank + gas[i] - cost[i]
            if tank < 0:
                tank = 0
                start = i + 1

        return start

435. Non-overlapping Intervals

Remove the fewest overlapping intervals. Sort by start time and compare each interval with the one currently retained. When they overlap, remove one and retain the smaller end because it leaves the most room for every later interval.

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });
        // No need to keep the retained intervals, only prevEnd.
        int prevEnd = intervals[0][1];
        int res = 0;

        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if (start < prevEnd) {
                res++;
                prevEnd = Math.min(prevEnd, end);
            } else {
                prevEnd = end;
            }
        }

        return res;
    }
}

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        # no need to keep actual list of merged intervals, just need prev_end!
        prev_end = intervals[0][1]
        res = 0

        for i in range(1, len(intervals)):
            start, end = intervals[i]

            if start < prev_end:
                res += 1
                prev_end = min(prev_end, end)
            else:
                prev_end = end

        return res

763. Partition Labels

Split a string so each character appears in at most one part. Record every character’s last occurrence, then extend the current partition boundary whenever a character inside it ends later. Reaching the boundary completes the earliest valid partition.

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> letToRight = new HashMap<>();
        for (int idx = 0; idx < s.length(); idx++) {
            char letter = s.charAt(idx);
            letToRight.put(letter, idx);
        }

        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int idx = 0; idx < s.length(); idx++) {
            char letter = s.charAt(idx);
            end = Math.max(end, letToRight.get(letter));
            if (end == idx) {
                res.add(end - start + 1);
                start = idx + 1;
            }
        }

        return res;
    }
}

from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        let_to_right = {}
        for idx, letter in enumerate(s):
            let_to_right[letter] = idx

        res = []
        start = 0
        end = 0
        for idx, letter in enumerate(s):
            end = max(end, let_to_right[letter])
            if end == idx:
                res.append(end-start+1)
                start = idx+1

        return res