Assign Cookies

Assign Cookies is a gentle introduction to greedy + two pointers. The trick is to stop thinking about clever combinations and instead make the locally best choice at every step — give each child the smallest cookie that still keeps them happy.

The slow way first

You might try every assignment of cookies to children and pick the best — but that explodes combinatorially. Even matching with backtracking is wasteful. The structure of the problem is simpler than it looks: a child only cares whether the cookie is big enough, nothing else.

The question to ask: which cookie should I spend on the easiest-to-please child? Spending a huge cookie on a child who only needs a tiny one is waste. So we want the smallest cookie that still satisfies each child.

The idea: sort, then sweep with two pointers

Sort both arrays ascending. Walk a pointer child over the greed factors and a pointer cookie over the sizes. For the current child, look at the current cookie:

• If the cookie is big enough (s[cookie] >= g[child]), this child is content — advance both pointers.
• If the cookie is too small, no later child (who is greedier) can use it either, so discard it — advance only cookie.

Greedy works here because giving the smallest sufficient cookie to the least greedy child never blocks a better future assignment — any cookie we discard was too small for everyone remaining.

Walk through it

Step through the animation. The top row is children greed, the bottom row is cookie sizes, both sorted. The g pointer moves through children and s through cookies. When a cookie fits, both pointers slide right and satisfied ticks up; when a cookie is too small it turns gray and only s moves on.

Pseudocode

sort g ascending           # children greed factors
sort s ascending           # cookie sizes
child = 0, cookie = 0
while child < len(g) and cookie < len(s):
    if s[cookie] >= g[child]:   # cookie big enough
        child += 1              # this child is content
        cookie += 1             # use up the cookie
    else:
        cookie += 1             # too small, discard it
return child                   # number of content children

The Python solution

def find_content_children(g, s):
    g.sort()
    s.sort()
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
            cookie += 1
        else:
            cookie += 1
    return child

• We sort both arrays so we can sweep from smallest to largest.
• child counts content children and also indexes the next child to satisfy; cookie indexes the next cookie to try.
• Line 6 is the greedy test: if the current cookie satisfies the current child, both advance.
• When the cookie is too small we drop it (advance cookie only) because it cannot help any greedier child later.
• The loop ends when we run out of children or cookies; child is the count of content children.

Complexity

The sort dominates, so the whole thing is O(n log n) time and O(1) extra space (ignoring the sort). The sweep itself is linear because neither pointer ever moves backward.

When this pattern shows up

Practice