Greedy Mastery: Array Adjustments and Niche Problems

Wiggle Subsequence (LeetCode 376)

Find the length of the longest wiggle subsequence, where the differences between successive numbers strictly alternate between positive and negative.

Greedy Logic: Count only the "turning points." We ignore elements that continue in the same direction and only increment our count when a peak or a valley is encountered.

public int wiggleMaxLength(int[] nums) {
    if (nums.length < 2) return nums.length;
    
    // up: length of wiggle ending with a rise
    // down: length of wiggle ending with a fall
    int up = 1, down = 1;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            up = down + 1;
        } else if (nums[i] < nums[i - 1]) {
            down = up + 1;
        }
    }
    return Math.max(up, down);
}

Video Stitching: Minimal Coverage (LeetCode 1024)

Given a set of clips [start, end], find the minimum number of clips to cover the interval [0, T].

Greedy Strategy:

1. Sort clips by their start times.
2. Within the currently covered range [0, curEnd], find the clip that has the furthest possible end.
3. Update curEnd to that furthest point and increment count.

public int videoStitching(int[][] clips, int time) {
    // Sort by start transition point
    Arrays.sort(clips, (a, b) -> Integer.compare(a[0], b[0]));
    
    int count = 0, currentEnd = 0, nextFarthest = 0, i = 0;
    
    while (currentEnd < time) {
        // Find the clip that extends the furthest among all available starts
        while (i < clips.length && clips[i][0] <= currentEnd) {
            nextFarthest = Math.max(nextFarthest, clips[i][1]);
            i++;
        }
        
        // If the furthest coverage didn't advance, coverage is broken
        if (nextFarthest <= currentEnd) return -1;
        
        count++;
        currentEnd = nextFarthest;
    }
    return count;
}

Can Place Flowers (LeetCode 605)

A flowerbed has 0s (empty) and 1s (filled). No two flowers can be adjacent. Can you plant $n$ more?

Greedy Logic: Scan from left to right. Whenever you see a 0 that is surrounded by 0s (or boundaries), plant a flower immediately. This greedy decision never prevents a later planting that would otherwise have been possible.

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int count = 0;
    for (int i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i] == 0) {
            boolean leftEmpty = (i == 0 || flowerbed[i - 1] == 0);
            boolean rightEmpty = (i == flowerbed.length - 1 || flowerbed[i + 1] == 0);
            if (leftEmpty && rightEmpty) {
                flowerbed[i] = 1; // Plant it!
                count++;
            }
        }
    }
    return count >= n;
}

Optimal Account Balancing (LeetCode 465)

Minimize transactions to settle all debts. This involves calculating net balances and then matching creditors with debtors.

Greedy/Backtracking:

• Calculate net balance for each person.
• Non-zero balances represent debt/credit.
• Use DFS to find the combination of matches that results in the fewest steps.

public int minTransfers(int[][] transactions) {
    Map<Integer, Integer> balanceMap = new HashMap<>();
    for (int[] t : transactions) {
        balanceMap.put(t[0], balanceMap.getOrDefault(t[0], 0) - t[2]);
        balanceMap.put(t[1], balanceMap.getOrDefault(t[1], 0) + t[2]);
    }
    
    List<Integer> debts = new ArrayList<>();
    for (int bal : balanceMap.values()) if (bal != 0) debts.add(bal);
    
    return backtrack(0, debts);
}

private int backtrack(int start, List<Integer> debts) {
    while (start < debts.size() && debts.get(start) == 0) start++;
    if (start == debts.size()) return 0;
    
    int minSteps = Integer.MAX_VALUE;
    for (int i = start + 1; i < debts.size(); i++) {
        // Match a debtor with a creditor (signs must differ)
        if (debts.get(start) * debts.get(i) < 0) {
            debts.set(i, debts.get(i) + debts.get(start));
            minSteps = Math.min(minSteps, 1 + backtrack(start + 1, debts));
            debts.set(i, debts.get(i) - debts.get(start)); // Undo
        }
    }
    return minSteps;
}

Performance Summary Table

Final Takeaway

The power of Greedy lies in finding the Infallible Choice: an action that is locally optimal and mathematically guaranteed not to hinder future progress. If you can prove that following the current "best" doesn't close any doors, Greedy is your tool. 筋