Assign Cookies
Assign Cookies: child i is content if they get a cookie of size at least their greed g[i]. Each child gets at most one cookie. Maximize the number of content children.
- 1 <= g.length <= 3 * 10⁴
- 0 <= s.length <= 3 * 10⁴
- 1 <= g[i], s[j] <= 2³¹ - 1
Intuition
Assign cookies matches cookies to children, where child i is satisfied by any cookie of size at least their greed g[i], and each child gets at most one. Maximise the number of satisfied children.
The instinct that works is to avoid waste. Handing a large cookie to a child who would have been happy with a small one throws away the only cookie that might satisfy a greedier child later. So pair small with small and keep the large cookies in reserve.
Sort both lists and walk them together, giving each child the smallest cookie that still satisfies them.
Why that is provably optimal, rather than merely sensible, is worth a moment. Take any optimal assignment and look at the least greedy unsatisfied child. If the optimum gives some child a cookie larger than necessary, swap it for the smallest sufficient one:
- The swap never satisfies fewer children, since the displaced larger cookie can still serve whoever held the smaller one.
Repeating that exchange turns any optimum into the greedy solution without ever losing a match, so greedy achieves the maximum too.
The implementation is two pointers over the sorted lists. Advance the cookie pointer always; advance the child pointer only when a cookie satisfies them. A cookie too small for the current child is too small for every remaining child as well — they are all greedier — so it is discarded permanently.
Two sorted lists walked with two pointers — the assign cookies greedy algorithm rests on an exchange argument. Give the smallest adequate cookie to the least demanding child: any other assignment can be swapped for this one without losing a match, so greedy is provably optimal. That swap argument is the standard way to prove a greedy is safe.
Approach
Before reading on: price up what the direct approach costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n log n + m log m) time and O(1) space.
Sort both lists
Sort the greed factors and the cookie sizes ascending. Both must be sorted — the two-pointer walk relies on being able to discard a cookie permanently, which is only safe when the remaining children are all greedier.
Walk with two pointers
Keep an index into each list. Compare the current cookie against the current child's greed, and decide from that single comparison whether the cookie is usable.
Advance the child only on a match
If the cookie satisfies the child, count them and move both pointers. If not, move only the cookie pointer — that cookie is too small for every remaining child, so it is discarded for good.
Understand the exchange argument
Any optimal assignment can swap an oversized cookie for the smallest sufficient one without satisfying fewer children, since the displaced cookie still covers the other child. Repeating that turns an optimum into the greedy answer.
Read the count from the child pointer
Every advance of the child pointer is one satisfied child, so its final value is the answer. No separate counter is needed, and the loop ends when either list runs out.
Cost of the approach
Sorting dominates at O(n log n + m log m), followed by a single O(n + m) pass. Space is O(1) beyond the sort, since only two indices are kept.
Solution & live demo
Common pitfalls
Assigning the largest cookies first
g.sort(reverse=True) s.sort(reverse=True)
g.sort() s.sort()
Spending a big cookie on a child a small one would satisfy wastes capacity that a greedier child may need. Ascending order guarantees each cookie goes to the least demanding child it can still satisfy.
Advancing the child pointer on a failed match
for cookie in s:
if g[child] <= cookie: child += 1
else: child += 1if child < len(g) and g[child] <= cookie:
child += 1A child that this cookie can't satisfy should stay in line for a bigger one, not be skipped. Only a successful assignment advances the child.
Indexing past the end of the children list
if g[child] <= cookie:
if child < len(g) and g[child] <= cookie:
With more cookies than children the loop keeps running after every child is served, and g[child] goes out of range. The bound check has to come first.
Edge cases
The loop body never feeds anyone — return 0.
Every comparison fails; child never advances; answer 0.
Once child == len(g) everyone is fed — break early; extra cookies are irrelevant.