Assign Cookies: Greedy Two-Pointer Matching

You are a parent with a set of cookies. Each child i has a greed factor g[i], the minimum cookie size that will make them content. Each cookie j has a size s[j]. A child is content only if you give them a cookie with s[j] >= g[i]. Each child gets at most one cookie, and each cookie goes to at most one child. Maximize the number of content children.

This is LeetCode 455: Assign Cookies, an easy problem that introduces greedy matching. The solution is short, but the reasoning behind why the greedy choice works is what makes it worth studying.

Why this problem matters

Assign Cookies is a clean introduction to the greedy paradigm. Many greedy problems require you to prove that a locally optimal choice leads to a globally optimal result, and this one has a particularly intuitive proof. If you have not worked with greedy algorithms before, this is the right place to start.

The pattern of sorting both inputs and using two pointers to match them greedily appears in problems like Non-overlapping Intervals, Task Scheduler, and Meeting Rooms. Getting comfortable with the logic here makes those harder problems more approachable.

The key insight: sort and match greedily

Sort both arrays in ascending order. Then walk through them with two pointers: one for children, one for cookies. At each step, try to assign the current cookie to the current child. If the cookie is big enough (s[cookie] >= g[child]), assign it and move both pointers. If not, the cookie is too small for this child (and every remaining child, since children are sorted by greed), so skip the cookie and move only the cookie pointer.

This greedy choice is optimal because wasting a large cookie on an easy-to-please child can never help. If a small cookie can satisfy the current child, there is no benefit in saving it. And if a cookie cannot satisfy the least greedy remaining child, it cannot satisfy any remaining child at all.

The greedy solution

def findContentChildren(self, g, s):
    g.sort()
    s.sort()
    child = 0
    cookie = 0

    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1

    return child

Why this greedy approach works

The argument has two parts.

Part 1: sorting does not lose solutions. The problem does not care which specific cookie goes to which specific child. It only asks for the count of content children. So we are free to rearrange both arrays however we like.

Part 2: the greedy choice is safe. After sorting, consider the least greedy child. If the smallest cookie satisfies them, assigning it is always at least as good as any other assignment. Using a bigger cookie on this child would satisfy them just the same, but it wastes a cookie that might have satisfied a greedier child later. If the smallest cookie does not satisfy the least greedy child, it cannot satisfy any child (since all others are greedier), so discarding it loses nothing.

By induction, repeating this greedy choice for each child in order of increasing greed produces the maximum number of content children.

Walking through it step by step

Let's trace through g = [1, 2, 3] and s = [1, 1]. The answer is 1.

After sorting, we start with both pointers at index 0. Cookie size 1 satisfies child greed 1, so we assign it and advance both pointers. The next cookie (size 1) cannot satisfy child greed 2, so we skip the cookie. We run out of cookies, and the loop ends. One child was made content.

Complexity analysis

The two-pointer scan itself is O(n + m), but sorting dominates. This is optimal because any solution must at least read all inputs, and comparison-based sorting has an O(n log n) lower bound.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy matching with sorting

Sort the inputs so that the optimal pairing becomes easy to find with a single scan. This pattern appears whenever you need to match elements from two sets and the problem has an exchange argument: swapping any non-greedy assignment can only make things worse (or no better).

a.sort()
b.sort()
i, j = 0, 0
while i < len(a) and j < len(b):
    if can_match(a[i], b[j]):
        i += 1
    j += 1

2. Two-pointer scan on sorted arrays

After sorting, use two pointers that only move forward. One pointer advances when a match is found, the other advances unconditionally. This gives a linear scan over both arrays, and the total work is bounded by O(n + m).

Edge cases

Before submitting, make sure your solution handles these:

• No cookies g = [1, 2], s = []: the while loop never executes. Return 0.
• No children g = [], s = [1, 2]: the while loop never executes. Return 0.
• All cookies too small g = [3, 4], s = [1, 2]: no cookie satisfies any child. The cookie pointer reaches the end without the child pointer ever advancing. Return 0.
• All children satisfied g = [1, 2], s = [1, 2, 3]: both children are content. Extra cookies are unused. Return 2.
• Equal greed and size g = [1, 1, 1], s = [1, 1, 1]: each cookie exactly satisfies one child. Return 3.
• Single child, single cookie g = [5], s = [5]: exact match. Return 1.

The greedy solution handles all of these without special-case logic.

From understanding to recall

You have read the greedy solution and it makes sense. Sort, two pointers, done. But can you write it from scratch in an interview without looking at it?

The details matter: remembering to sort both arrays (not just one), advancing the child pointer only on a successful match, always advancing the cookie pointer, and returning child (not cookie). These are small points, but under pressure they are easy to mix up if you have not practiced writing the code from memory.

Spaced repetition closes that gap. You practice writing the greedy two-pointer loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "match elements from two sorted sets" and the code flows out without hesitation.

The greedy matching pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Non-overlapping Intervals
• Jump Game
• Candy