Assign Cookies
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 a matching problem: pair children with cookies so that each paired cookie is at least as large as its child's greed factor, and maximize the number of pairs.
A large cookie spent on a child who would accept a smaller one is wasted, because that cookie might be the only one big enough for a pickier child. Avoiding this waste suggests a greedy strategy: sort both lists, satisfy the least greedy children first, and give each child the smallest cookie that works.
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; the answer is then 0.1 <= g[i], s[j] <= 2^31 - 1→ Values can reach the maximum 32-bit integer, but since we only compare sizes (no arithmetic), overflow isn't a concern.
Approach 1: Brute Force
Intuition
For each child, scan the cookies and take the first unused one that is big enough. Sort both arrays first: children are then processed from least to most greedy, and the first unused cookie that fits is also the smallest one that fits, so no large cookie is spent where a small one would do.
Each child may scan the entire cookie array, so the matching step costs O(n * m) on top of the sorting, where n is the number of children and m is the number of cookies.
Algorithm
- Sort both
g(greed factors) ands(cookie sizes) in ascending order. - Create a boolean array
usedof size m (number of cookies), initialized to all false. - Initialize
contentChildren = 0. - For each child (in sorted order of greed):
- Scan the cookies from smallest to largest and take the first unused cookie with
s[j] >= g[i]. - If one exists, mark it as used and increment
contentChildren. - Return
contentChildren.
Example Walkthrough
Code
- 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
usedboolean array tracks which cookies have been assigned.
The sorting already does most of the work here. Once a cookie fails the current child, it fails every remaining child too, since the children are sorted by greed. A single forward pass over both arrays, never revisiting a cookie, replaces the nested scan.
Approach 2: Greedy with Two Pointers (Optimal)
Intuition
With both arrays sorted, walk through them in lockstep, starting with the least greedy child and the smallest cookie. If the current cookie satisfies the current child, assign it and advance both pointers. If it is too small, advance only the cookie pointer: a cookie that cannot satisfy the least greedy remaining child cannot satisfy anyone else, so it can be discarded permanently.
Every cookie and every child is visited at most once, so the pass after sorting is linear in n + m.
Two swap arguments show the greedy choice is safe. First, take any assignment that achieves the maximum count. If it satisfies some child but not a less greedy one, the less greedy child can take that cookie instead, so a maximum assignment exists that satisfies the least greedy children. Second, if a satisfied child holds a larger cookie than the smallest sufficient one while that smallest cookie sits elsewhere, swapping the two cookies keeps everyone satisfied, because the other holder only ever receives a larger cookie. Both swaps preserve the count, so matching the least greedy unmatched child with the smallest cookie that fits, which is what the two-pointer pass does, always reaches the maximum.
Algorithm
- Sort both
g(greed factors) ands(cookie sizes) in ascending order. - Initialize two pointers:
childIndex = 0(points to the current child) andcookieIndex = 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
Code
- 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) extra space beyond what the sorting routine itself uses. Only two integer pointers are maintained, and both arrays are sorted in place.