Core Idea of Greedy Algorithms

The essence of a greedy strategy is to build a globally optimal solution by repeatedly making locally optimal choices. The typical workflow involves:

1. Breaking the problem into smaller subproblems.
2. Determining a suitable greedy criterion.
3. Obtaining the best posssible choice for each subproblem.
4. Aggregating these local decisions into a global answer.

Care must be taken because greedy methods do not work for every problem — it is advised to think of counterexamples before adopting this approach.

Assigning Cookies to Children (LeetCode 455)

Given two arrays: children (minimum cookie size each child needs) and cookies (available cookie sizes), we aim to maximise the number of content children. A natural greedy strategy is to give the smallest feasible cookie to the child with the smallest appetite.

Sort both arrays, then use two pointers to iterate through them:

def assign_cookies(children, cookies):
    children.sort()
    cookies.sort()
    child_ptr = cookie_ptr = 0
    while child_ptr < len(children) and cookie_ptr < len(cookies):
        if cookies[cookie_ptr] >= children[child_ptr]:
            child_ptr += 1
        cookie_ptr += 1
    return child_ptr

The child pointer only advances when a suitable cookie is41 found, while the cookie pointer moves forward regardless. The returned value is the05 count of satisfied children.

Longest Wiggle Subsequence (LeetCode 376)

A wiggle sequence is one where successive differences alternate between positive and negative. The goal is to find the length of the longest subsequence with this property. The greedy idea: eliminate all intermediate points on a monotonic slope, retaining only the local peaks and valleys, because42 those define the switches in direction.

We can track the previous difference (prev_diff) and the current difference (curr_diff). A new wiggle is detected when one difference is non‑zero and the product prev_diff * curr_diff is ≤ 0. Initially, prev_diff is 0 to handle the first point. The count starts at 1 (the first element always counts).

def wiggle_max_length(nums):
    if len(nums) < 2:
        return len(nums)
    prev_diff = 0
    wiggle_count = 1
    for i in range(1, len(nums)):
        curr_diff = nums[i] - nums[i - 1]
        if curr_diff != 0 and prev_diff * curr_diff <= 0:
            wiggle_count += 1
            prev_diff = curr_diff
    return wiggle_count

Maximum Subarray Sum (LeetCode 53)

Given an integer array, find the contiguous subarray with the largest sum. The greedy appproach: whenever the running sum becomes negative, discard it and start fresh from the next element, because a negative prefix can only reduce the sum of any subsequent extension.

We maintain a variable max_sum initialized to negative infinity and a current_sum that accumulates values. After adding each number, we update max_sum if current_sum is larger. If current_sum drops below zero, we reset it to zero, effectively moving the start of the subarray.

def max_subarray_sum(nums):
    max_sum = float('-inf')
    current_sum = 0
    for num in nums:
        current_sum += num
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < 0:
            current_sum = 0
    return max_sum