Assign Cookies: Greedy Sorting Strategy Explained (With Proof)

Assign Cookies (LeetCode #455) is the perfect introduction to greedy with sorting. It teaches you the fundamental pattern: sort both arrays, match smallest to smallest.

This problem appears simple, but understanding why the greedy approach works builds intuition for harder problems.

TL;DR

Strategy: Sort both children's greed and cookie sizes ascending. Match smallest greed with smallest satisfying cookie.

Why it works: If cookie j can't satisfy child i, it can't satisfy any child with higher greed.

Time: O(n log n + m log m), Space: O(1)

The Problem

LeetCode #455: Assign Cookies

You have:

• g[i]: greed factor of child i (minimum cookie size to satisfy)
• s[j]: size of cookie j

Goal: Maximize number of satisfied children.

Constraint: Each child gets at most one cookie, each cookie to at most one child.

Example:

g = [1, 2, 3]  # Children's greed
s = [1, 1]     # Cookie sizes

Output: 1
Explanation: Only one child can be satisfied (greed=1 with cookie=1)

The Greedy Solution

def findContentChildren(g, s):
    """
    Time: O(n log n + m log m)
    Space: O(1) excluding sort
    """
    g.sort()  # Greed factors ascending
    s.sort()  # Cookie sizes ascending
    
    child = 0
    cookie = 0
    
    while child < len(g) and cookie < len(s):
        # If current cookie satisfies current child
        if s[cookie] >= g[child]:
            child += 1  # Move to next child
        cookie += 1     # Move to next cookie
    
    return child  # Number of satisfied children

Why This Works: The Greedy Insight

Key observation: If we give a large cookie to a child with small greed, we waste resources.

Greedy choice: Always try to satisfy the child with smallest greed using the smallest cookie that works.

Why it's optimal:

1. If cookie s[j] can't satisfy child g[i], it can't satisfy any child g[k] where k > i (since array is sorted)
2. If cookie s[j] can satisfy child g[i], using it for g[i] is optimal (don't save it for later)
3. Matching smallest-to-smallest maximizes future options

Step-by-Step Trace

g = [1, 2, 3]
s = [1, 1, 2]

After sort:
g = [1, 2, 3]
s = [1, 1, 2]

Step 1: child=0, cookie=0
  g[0]=1, s[0]=1
  1 >= 1? YES
  Satisfy child 0 with cookie 0
  child=1, cookie=1

Step 2: child=1, cookie=1
  g[1]=2, s[1]=1
  1 >= 2? NO
  Skip cookie 1
  child=1, cookie=2

Step 3: child=1, cookie=2
  g[2]=2, s[2]=2
  2 >= 2? YES
  Satisfy child 1 with cookie 2
  child=2, cookie=3

Step 4: cookie=3 >= len(s)
  Stop

Result: 2 children satisfied

Proof of Correctness

Claim: Greedy matching (smallest-to-smallest) gives maximum satisfied children.

Proof by Exchange Argument:

Suppose optimal solution O uses different matching. Let G be greedy solution.

Case 1: O matches child g[i] with cookie s[j], where j is not the smallest cookie that satisfies g[i].

Let s[k] be the smallest cookie satisfying g[i] (where k < j).

Exchange: Swap cookies in O:

• Give s[k] to child g[i] instead of s[j]
• Give s[j] to whoever had s[k]

Result: Still valid (since s[j] >= s[k] >= g[i]) and uses same number of cookies.

Repeat until O matches G.

Conclusion: Greedy is optimal. ✓

Alternative Proof: Greedy Choice Property

Greedy Choice Property: Making locally optimal choice (smallest cookie for smallest greed) leads to globally optimal solution.

Proof:

1. Let g[0] be smallest greed
2. Let s[k] be smallest cookie satisfying g[0]
3. Claim: There exists an optimal solution using s[k] for g[0]

Why?

• If optimal uses different cookie s[j] for g[0] (where j > k), we can swap
• s[k] works for g[0] (since s[k] >= g[0])
• s[j] can replace s[k] elsewhere (since s[j] >= s[k])
• Still optimal after swap

Induction: Apply same logic to remaining children and cookies. ✓

Why NOT Other Strategies?

Strategy 1: Match Largest to Largest

❌ Wrong:

g.sort(reverse=True)
s.sort(reverse=True)

Counterexample:

g = [1, 2, 10]
s = [1, 2, 3]

Largest-first:
  Match g[2]=10 with s[2]=3? NO
  Match g[2]=10 with s[1]=2? NO
  Match g[2]=10 with s[0]=1? NO
  Match g[1]=2 with s[2]=3? YES (1 satisfied)
  Match g[0]=1 with s[1]=2? YES (2 satisfied)

Smallest-first (greedy):
  Match g[0]=1 with s[0]=1? YES
  Match g[1]=2 with s[1]=2? YES
  Match g[2]=10 with s[2]=3? NO
  Result: 2 satisfied (same)

But for g=[1,2,3], s=[1,1,2]:
  Largest-first: 1 satisfied
  Smallest-first: 2 satisfied ✓

Strategy 2: No Sorting

❌ Wrong:

# Just iterate without sorting

Why it fails: Can't make optimal local decisions without knowing relative ordering.

Code in Multiple Languages

JavaScript:

function findContentChildren(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    
    let child = 0;
    let cookie = 0;
    
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {
            child++;
        }
        cookie++;
    }
    
    return child;
}

Java:

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    
    int child = 0;
    int cookie = 0;
    
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {
            child++;
        }
        cookie++;
    }
    
    return child;
}

Common Mistakes

Mistake 1: Wrong Comparison

❌ Wrong:

if s[cookie] > g[child]:  # Should be >=

✅ Correct:

if s[cookie] >= g[child]:

Mistake 2: Incrementing Both Pointers Always

❌ Wrong:

child += 1
cookie += 1  # Always increment both

✅ Correct:

if s[cookie] >= g[child]:
    child += 1  # Only if satisfied
cookie += 1     # Always try next cookie

Mistake 3: Not Sorting

❌ Wrong:

# Forgot to sort!
while child < len(g) and cookie < len(s):
    ...

✅ Correct:

g.sort()
s.sort()
while child < len(g) and cookie < len(s):
    ...

The Pattern: Greedy Two-Array Matching

This problem teaches a general pattern:

When to use:

• Two arrays to match
• Maximize/minimize matches
• Each element used at most once

Template:

arr1.sort()
arr2.sort()

i = j = 0
count = 0

while i < len(arr1) and j < len(arr2):
    if can_match(arr1[i], arr2[j]):
        count += 1
        i += 1
        j += 1
    else:
        j += 1  # Or i += 1, depending on problem

return count

Similar problems:

• Two City Scheduling (LC #1029)
• Boats to Save People (LC #881)
• Advantage Shuffle (LC #870)

Complexity Analysis

Time Complexity:

• Sort g: O(n log n)
• Sort s: O(m log m)
• Two-pointer scan: O(n + m)
• Total: O(n log n + m log m)

Space Complexity:

• Sorting: O(1) if in-place, O(n + m) if not
• Pointers: O(1)
• Total: O(1) excluding sort

Conclusion

Assign Cookies demonstrates the power of greedy with sorting:

1. Sort both arrays
2. Match smallest to smallest
3. Proof: exchange argument or greedy choice property

This pattern appears in many interview problems. Master it here, apply it everywhere.

For more on greedy with sorting, see Greedy with Sorting Template and the complete greedy guide.