DSA problem
Assign Cookies
Assume you are an awesome parent and want to give cookies to your children. Each child i has a greed factor g[i], the minimum size of a cookie that will content them, and each cookie j has a size s[j]. If s[j] >= g[i], you may assign cookie j to child i and the child becomes content. Each child can receive at most one cookie. Your goal is to maximize the number of content children and return that maximum.
The problem is a classic assignment task that hides a clean greedy structure. Because each child consumes exactly one cookie and each cookie can satisfy at most one child, no clever combinatorial swap can ever beat a strategy that locally picks the best available match. The challenge is choosing what "best" means so the greedy choice does not block future matches.
The trick is to sort both arrays in ascending order and then walk them with two pointers. Always try to satisfy the least greedy remaining child with the smallest cookie that fits. If the current cookie is too small, skip it — no smaller child remains to use it later because we already processed everyone with a smaller greed. If it fits, count a content child and advance both pointers; otherwise advance only the cookie pointer.
This pairing is optimal by an exchange argument: any optimal solution that assigns a larger cookie to an easy child can be re-paired with the smallest sufficient cookie without losing any contentment. Sorting costs O(n log n + m log m) and the two-pointer pass costs O(n + m), giving total O(n log n + m log m) time with O(1) extra space beyond the sort.
Examples
g = [1,2,3], s = [1,1]1g = [1,2], s = [1,2,3]2g = [10,9,8,7], s = [5,6,7,8]2Constraints
- 1 <= g.length <= 3 * 10^4
- 0 <= s.length <= 3 * 10^4
- 1 <= g[i], s[j] <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.