#455
Assign Cookies
Easy Sort + match smallest
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each child needs a cookie of at least their greed size; each cookie has a size and goes to at most one child. Maximise the number of content children.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: feed as many children as possible.
Why this works: give each child the smallest cookie that is big enough, so the big cookies are saved for greedier kids.
Example: greed [1, 2, 3], cookies [1, 1]
child 1 gets cookie 1child 2: remaining cookie 1 too small → 1 content child
✦Hints open one at a time
Sort both arrays.
Give each child the smallest cookie that satisfies them.
↗Approach
Two pointers over sorted greed and sizes: if the current cookie satisfies the current child, both move on; otherwise try the next (bigger) cookie.
</>Solution (Java)
import java.util.*;
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int child = 0;
for (int cookie = 0; cookie < s.length && child < g.length; cookie++) {
if (s[cookie] >= g[child]) child++; // smallest cookie that fits
}
return child;
}
}!Common mistake
Giving the biggest cookie to the first child — it might be needed for a greedier child.
Complexity
- Time: O(n log n + m log m).
- Space: O(1) besides sorting.
Topic: Greedy
🎬 Episodes 69–73: video coming soon