How do you approach Assign Cookies?

Sort both arrays, then walk them with one pointer each.

What is the time complexity of Assign Cookies?

Time complexity: O(n log n + m log m), dominated by the sorts.. Space complexity: O(1) beyond the sorts..

What are common mistakes on Assign Cookies?

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem. Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic. Missing the case where two greedy choices tie and the tiebreak decides correctness.

gitGood.dev

← Back to problems

Assign Cookies

EasyAlgorithms

Description

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.

Example 1

Input: g = [1,2,3], s = [1,1]

Output: 1

Example 2

Input: g = [1,2], s = [1,2,3]

Output: 2

Example 3

Input: g = [10,9,8,7], s = [5,6,7,8]

Output: 2

Constraints

- 0 <= g.length <= 3 * 10^4 - 0 <= s.length <= 3 * 10^4 - 1 <= g[i], s[j] <= 2^31 - 1

Assign Cookies: approach, complexity and pitfalls

An easy greedy problem, graded against 6 test cases (3 of them hidden).

The pattern: Greedy

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 Greedyproblems →

If you are stuck

Show the 3-step hint ladder

Sort both arrays, then walk them with one pointer each.
Always give the least greedy remaining child the smallest cookie that satisfies them - spending a large cookie on a small appetite wastes it.
If the current cookie is too small for the current child, no later child can use it either (they are greedier), so discard it and move on.

The optimal approach

Show the approach: Greedy, justified by an exchange argument

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.

Time: O(n log n + m log m), dominated by the sorts.
Space: O(1) beyond the sorts.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Greedy mistakes

These apply to the pattern as a whole, not just this problem.

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem.
Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic.
Missing the case where two greedy choices tie and the tiebreak decides correctness.

← Back to problems

Assign Cookies

EasyAlgorithms

Description

Example 1

Input: g = [1,2,3], s = [1,1]

Output: 1

Example 2

Input: g = [1,2], s = [1,2,3]

Output: 2

Example 3

Input: g = [10,9,8,7], s = [5,6,7,8]

Output: 2

Constraints

- 0 <= g.length <= 3 * 10^4 - 0 <= s.length <= 3 * 10^4 - 1 <= g[i], s[j] <= 2^31 - 1

Assign Cookies: approach, complexity and pitfalls

An easy greedy problem, graded against 6 test cases (3 of them hidden).

The pattern: Greedy

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 Greedyproblems →

If you are stuck

Show the 3-step hint ladder

Sort both arrays, then walk them with one pointer each.
Always give the least greedy remaining child the smallest cookie that satisfies them - spending a large cookie on a small appetite wastes it.
If the current cookie is too small for the current child, no later child can use it either (they are greedier), so discard it and move on.

The optimal approach

Show the approach: Greedy, justified by an exchange argument

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.

Time: O(n log n + m log m), dominated by the sorts.
Space: O(1) beyond the sorts.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Greedy mistakes

These apply to the pattern as a whole, not just this problem.

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem.
Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic.
Missing the case where two greedy choices tie and the tiebreak decides correctness.