You are handing out cookies to children. Child i will only be content with a cookie whose size is at least their greed factor g[i], and each cookie s[j] can go to at most one child.
Given the greed factors g and the cookie sizes s, return the maximum number of children you can content.
Input: g = [1,2,3], s = [1,1] Output: 1 Three children with greed 1,2,3 and two cookies of size 1. Only the child with greed 1 can be content.
Input: g = [1,2], s = [1,2,3] Output: 2 Both children can be satisfied — greed 1 with a size-1 cookie and greed 2 with a size-2 cookie.
- 1 <= g.length <= 3 * 10^4 - 0 <= s.length <= 3 * 10^4 - 1 <= g[i], s[j] <= 2^31 - 1
To make as many children happy as possible, you should never "waste" a cookie. The greedy insight is to satisfy the least greedy remaining child with the smallest cookie that still works — saving every larger cookie for the harder-to-please children still waiting.
“Can one cookie satisfy more than one child?”
No — each cookie goes to at most one child, and each child needs at most one cookie.
“When is a child content?”
When the cookie's size is greater than or equal to that child's greed factor.
“What if there are no cookies?”
Then no child can be satisfied — the answer is 0.
“Do leftover cookies or children matter?”
No — you only count content children; extras of either are simply unused.
I'll sort both the children by greed and the cookies by size.
Then I walk the cookies from smallest up, giving each to the least greedy child it can satisfy.
Spending the smallest sufficient cookie keeps the bigger ones for greedier children — that's the greedy choice.
Worked example — g = [1, 2, 3], s = [1, 1]
sorted g: 1 2 3 sorted s: 1 1 cookie 1 vs child(greed 1): 1 >= 1 -> content! (children done: 1) cookie 1 vs child(greed 2): 1 < 2 -> discard cookie no cookies left -> stop answer: 1
The child easiest to please should be matched first: any cookie that can content a greedy child can also content a less greedy one, so saving cookies for the greedy children is never worse.
Among cookies that satisfy the current child, spend the smallest. Bigger cookies are strictly more valuable (they can satisfy strictly more children), so hoard them.
With both lists sorted, a two-pointer pass makes exactly these choices: advance the cookie pointer always, advance the child pointer only when the current cookie contents them.
| Match then scan | Sort + two pointers | |
|---|---|---|
| Idea | For each child, scan for the smallest unused cookie that fits | Sort both, sweep once matching greedily |
| Time | O(n * m) | O(n log n + m log m) |
| Space | O(m) used-flags | O(1) beyond sorting |
Both make the same greedy matches; sorting once lets the two-pointer version skip the repeated scans. Full code is in the Approaches selector below.
Key takeaway
Sort children by greed and cookies by size, then sweep: give the smallest sufficient cookie to the least greedy remaining child. Spending the smallest cookie that works — and never a bigger one — is the exchange argument that makes this greedy match optimal.
sort g ascending; sort s ascending
child = 0
for each cookie in s (ascending):
if child < len(g) and cookie >= g[child]:
child += 1 # content this child
return child