Assign Cookies

Easy

Sort both, feed the least greedy first

Problem

Each child i has greed g[i] and each cookie j has size s[j]. A child is content if a cookie's size >= their greed. Maximize the number of content children.

In simple words

Sort both, then give the smallest cookie that satisfies each least-greedy child.

The idea

Sort children by greed and cookies by size, then walk both giving the smallest adequate cookie to the least greedy remaining child. Spending a larger cookie on a child a smaller one would satisfy can never help, which is what makes the greedy choice safe.

The trick

Two pointers after sorting; advance the cookie pointer always, the child pointer only on a match.
O(n log n) dominated by the sorts.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n log n)spaceO(1)

1sort(g); sort(s)2i=j=03while i<len(g) and j<len(s):4  if s[j]>=g[i]: i++      // child content5  j++6return i

Input

array: [1, 2, 3]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: greed = [1, 2, 3], sizes = [1, 1]
Output:: 1
Explanation:: Only the child needing 1 can be fed.

Example 2

Input:: greed = [1, 2], sizes = [1, 2, 3]
Output:: 2
Explanation:: Both children get a big-enough cookie.

Example 3

Input:: greed = [2], sizes = [1]
Output:: 0
Explanation:: The cookie is too small → 0 fed.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.