Understanding the Problem

We have two lists: children (each with a minimum cookie size they'll accept) and cookies (each with a size). We need to match cookies to children so that the maximum number of children are satisfied. Each child gets at most one cookie, and each cookie goes to at most one child.

This is essentially a matching problem. We want to pair up children and cookies such that each paired cookie is large enough for its child, and we maximize the total number of pairings.

The key observation is that we should avoid wasting large cookies on children who would be happy with smaller ones. If a child only needs a cookie of size 1, giving them a cookie of size 10 wastes a resource that could satisfy a pickier child. This naturally leads to a greedy strategy: sort both lists and try to satisfy the least greedy children first, using the smallest cookies that work.

Key Constraints:

1 <= g.length <= 3 * 10^4 → With n up to 30,000, O(n log n) sorting is fine. O(n^2) brute force is borderline (up to 900 million operations) and likely too slow.
0 <= s.length <= 3 * 10^4 → The cookie array can be empty, which means the answer is 0. We need to handle this edge case.
1 <= g[i], s[j] <= 2^31 - 1 → Values can be very large, but since we only compare sizes (no arithmetic), overflow isn't a concern.

Approach 1: Brute Force

Intuition

The most natural first attempt: for each child, scan through all the cookies to find one that's big enough. Once a cookie is used, mark it as taken so no other child gets it. To maximize satisfied children, we should try to satisfy the least greedy children first (they're easier to please), so we sort the children array first.

This works correctly, but for each child we potentially scan through all cookies, giving us O(n * m) time where n is the number of children and m is the number of cookies.

Algorithm

Sort the greed factor array g in ascending order.
Create a boolean array used of size m (number of cookies), initialized to all false.
Initialize contentChildren = 0.
For each child (in sorted order of greed):

Scan through all cookies to find the smallest unused cookie that satisfies this child.
If found, mark that cookie as used and increment contentChildren.

Return contentChildren.

Example Walkthrough

1Sorted g=[1,2,3], s=[1,1]. Start with child 0 (greed=1)

child i=0

1/5

1Cookies sorted: [1, 1]. All unused.

1/5

Code

Complexity Analysis

Time Complexity: O(n log n + m log m + n m). Sorting both arrays takes O(n log n + m log m). The nested loop scans up to m cookies for each of n children, giving O(n m) as the dominant term.
Space Complexity: O(m). The used boolean array tracks which cookies have been assigned.

Since both arrays are sorted, once we pass a cookie that's too small for the current child, it's too small for all remaining children too. What if we just marched forward through both arrays simultaneously, never going back?

Approach 2: Greedy with Two Pointers (Optimal)

Intuition

Here's the core insight: if both arrays are sorted, we can walk through them in lockstep. Start with the least greedy child and the smallest cookie. If the smallest cookie satisfies the least greedy child, great, assign it and move on to the next child and next cookie. If the cookie is too small, skip it (it won't satisfy any remaining child either) and try the next cookie.

Why is this greedy strategy optimal? If a small cookie can satisfy a child, there's no benefit in saving that small cookie for a greedier child (who needs a bigger cookie anyway). And there's no benefit in using a larger cookie for a less greedy child when a smaller one would do, because that larger cookie might be the only one that satisfies a greedier child later. So by sorting both and matching smallest-to-smallest, we never waste resources.

Why does this work?

The greedy choice is provably optimal here. Suppose we have a different assignment that satisfies more children. In that assignment, some child C is satisfied by a cookie that's larger than what our greedy approach would assign. That means the greedy approach's smaller cookie was either unused or given to someone else. But since we process children in order of increasing greed, any child before C has equal or lesser greed, so swapping cookies between C and an earlier child won't reduce the total count. By an exchange argument, no alternative assignment can beat the greedy one.

In simpler terms: always giving the smallest sufficient cookie to the least greedy remaining child leaves the best options open for greedier children later. You never paint yourself into a corner.

Algorithm

Sort both g (greed factors) and s (cookie sizes) in ascending order.
Initialize two pointers: childIndex = 0 (points to the current child) and cookieIndex = 0 (points to the current cookie).
While both pointers are within bounds:

If s[cookieIndex] >= g[childIndex], the cookie satisfies the child. Move both pointers forward.
Otherwise, the cookie is too small. Move only the cookie pointer forward.

Return childIndex (the number of children satisfied).

Example Walkthrough

1Sorted: g=[1,2,3], s=[1,1]. childIndex=0, cookieIndex=0

childIndex

1/4

1Cookies sorted: [1, 1]. cookieIndex starts at 0.

cookieIndex

1/4

Code

Complexity Analysis

Time Complexity: O(n log n + m log m). Sorting the children array takes O(n log n) and sorting the cookies array takes O(m log m). The two-pointer pass is O(n + m), which is dominated by the sorting step.
Space Complexity: O(1). Only two integer pointers are used. The sorting is done in place.

Assign Cookies

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Greedy with Two Pointers (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium