AlgoViz
HomeDynamic Programming

Assign Cookies

Easy

Sort both, match greedily

Problem

Maximize the number of content children where a child with greed g[i] needs a cookie of size >= g[i].

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 and give each child the smallest cookie that satisfies it. Using a bigger cookie where a smaller one would do can never increase the count, so the greedy choice is safe.

The trick

  • Two pointers after sorting.
  • Greedy, not DP — the exchange argument proves optimality.

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.

1
2
3
0
1
2

Step 1 of 2. Here's the example — g=[1,2,3], s=[1,1] Values: 1, 2, 3.

1/2
Optimal
timeO(n log n)spaceO(1)
1sort both; two pointers assigning smallest fitting cookie

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.