Assign Cookies (LeetCode 455)

The problem

Each child i has a greed factor g[i]: the smallest cookie size that makes them happy. Each cookie j has a size s[j]. A child gets at most one cookie, and a cookie goes to at most one child. Return the maximum number of happy children.

Input:  g = [1, 2, 3], s = [1, 1]
Output: 1

Both cookies have size 1. Only the child with greed 1 can be satisfied; the other two need bigger cookies.

How to think about it

Start with brute force. Try every way of assigning cookies to children and keep the best count. That is a matching problem with factorially many assignments. Even a bipartite-matching algorithm is far heavier than this problem deserves.

The key insight: never waste a big cookie on a small appetite. Look at the least greedy child. Some cookie must be at least g[0] to please them. If you give them the smallest cookie that is big enough, every larger cookie is still free for greedier children. An exchange argument proves it: if an optimal answer gave that child a bigger cookie, swapping in the smaller one never makes anyone else worse off.

Sorting turns this into a two-pointer sweep. Sort g and s. Walk cookies from smallest to largest. If the current cookie satisfies the current (least greedy unfed) child, feed them and move to the next child. Either way the cookie is used up or useless: a cookie too small for the least greedy remaining child is too small for everyone after them.

Which pattern is this? Greedy with sort-then-sweep. The tell is “maximum number of pairs” where one side has a threshold the other side must meet.

Approach

1. Sort the greed factors g and the cookie sizes s ascending.
2. Keep i on the least greedy unfed child and j on the smallest unused cookie.
3. While both lists have items left: if s[j] >= g[i], the child is happy, so move i forward.
4. Always move j forward: the cookie was either eaten or too small to ever help.
5. i is the number of children fed.

Solution

def find_content_children(g, s):
    g.sort(); s.sort(); i = j = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:        # smallest cookie that satisfies the least greedy child
            i += 1
        j += 1                  # this cookie is used up or too small for anyone left
    return i
# find_content_children([1,2,3], [1,1]) -> 1

Dry run

With g = [1, 2, 3] and s = [1, 1] (already sorted):

j reaches the end of s, so the loop stops and the answer is 1.

Complexity

• Time: O(n log n + m log m). Sorting the two lists dominates; the sweep is linear because each pointer only moves forward.
• Space: O(1) extra. The pointers are the only state. Python’s sort uses O(n) auxiliary memory internally, which interviewers usually accept as “in place”.

Edge cases and pitfalls

• No cookies or no children returns 0: the loop never runs.
• Duplicates are fine; equal greeds or sizes just match one by one.
• Moving i instead of j on a miss is the classic bug. A too-small cookie should be discarded, not the child.
• Greedy from the wrong end (biggest cookie to the least greedy child) wastes cookies and gives wrong answers.
• Sorting mutates the input. Copy the lists first if the caller still needs them.

Related problems

• Candy (LeetCode 135): another greedy over children and ratings, solved with two sweeps.
• Hand of Straights (LeetCode 846): sort first, then always deal with the smallest remaining item.
• Non-overlapping Intervals (LeetCode 435): sort, then greedily keep the choice that leaves the most room.