We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Each child i has a greed factor g[i] - the minimum cookie size that will content them. Each cookie j has size s[j].
A child is content if assigned a cookie of size at least their greed factor. Each child gets at most one cookie and each cookie goes to at most one child.
Return the maximum number of children you can content.
An easy greedy problem, graded against 6 test cases (3 of them hidden).
Take the locally best option each step and prove it stays globally optimal.
Reach for it when you see: Interval scheduling, jump/reachability questions, or an optimisation with an obvious local choice.
More Greedy problems →Sort both arrays and advance two pointers. Offer the smallest remaining cookie to the least greedy remaining child: if it satisfies them, count it and advance both pointers; if not, discard the cookie and try the next one.
The reason discarding is safe is the sorted order - a cookie too small for the least greedy remaining child is too small for every remaining child, so it can never be useful.
The reason the greedy choice is optimal is an exchange argument, and it is worth being able to state: suppose an optimal solution gives a larger cookie to the least greedy child. Swapping it for the smallest cookie that satisfies them keeps that child content and frees a larger cookie for someone else, so the solution is no worse. Repeating the swap turns any optimal solution into the greedy one - which proves greedy is optimal rather than merely plausible.
That pattern - sort, then match smallest-to-smallest with an exchange argument - recurs across scheduling and assignment problems, and being able to justify it is usually what the interviewer is actually testing.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.