Greedy algorithms operate by making locally optimal choices at each step to achieve a global optimum. Unlike other algorithmic paradigms, they lack a universal pattern, making them either straightforward or challenging based on the problem.

Core Principles of Greedy Algorithms

Greedy strategies rely on selecting the best immediate option without reconsideration, aiming for an overall optimal solutoin. In practice, if manual simulatino suggests local optima lead to a global optimum without counterexamples, a greedy approach may be applicable.

Example Problems and Solutions

455. Assign Cookies

Distribute cookies to children greedily by matching smallest cookies to children with the least greed, maximizing satisfied children.

376. Wiggle Subsequence

Determine the longest subsequence where differences alternate between positive and negative. Track changes without altering the original array order.

int calculateWiggleLength(int[] values) {
    if (values.length < 2) return values.length;
    int prevDiff = 0;
    int length = 1;
    for (int i = 1; i < values.length; i++) {
        int currDiff = values[i] - values[i - 1];
        if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
            prevDiff = currDiff;
            length++;
        }
    }
    return length;
}

53. Maximum Subarray

Find the contiguous subarray with the largest sum. Reset the running sum if it becomes negative, but handle all-negative arrays by tracking the maximum element.

int findMaxSubarraySum(int[] elements) {
    int maxSum = Integer.MIN_VALUE;
    int currentSum = 0;
    for (int value : elements) {
        currentSum += value;
        maxSum = Math.max(maxSum, currentSum);
        if (currentSum < 0) {
            currentSum = 0;
        }
    }
    return maxSum;
}

122. Best Time to Buy and Sell Stock II

Maximize profit by summing all positive differences between consecutive days, allowing multiple transactions.

55. Jump Game

Check if you can reach the last index by iterating through the reachable range and updating the maximum jump distance.

boolean canReachEnd(int[] jumps) {
    int farthest = 0;
    for (int position = 0; position <= farthest; position++) {
        farthest = Math.max(farthest, position + jumps[position]);
        if (farthest >= jumps.length - 1) {
            return true;
        }
    }
    return false;
}

45. Jump Game II

Compute the minimum jumps to reach the end using greedy range expansion.

int minJumpsToEnd(int[] jumps) {
    int jumpsCount = 0;
    int currentEnd = 0;
    int farthest = 0;
    for (int i = 0; i < jumps.length - 1; i++) {
        farthest = Math.max(farthest, i + jumps[i]);
        if (i == currentEnd) {
            jumpsCount++;
            currentEnd = farthest;
        }
    }
    return jumpsCount;
}

1005. Maximize Sum Of Array After K Negations

Repeatedly negate the smallest element to maximize the sum after K operations.

134. Gas Station

Determine the starting gas station index to complete a circuit by checking cumulative gas balance.