Assign Cookies
Problem
Given two integer arrays g and s representing the greed factors of children and the sizes of cookies respectively, return the maximum number of children who can be content with the cookies provided such that each child is assigned at most one cookie and a cookie can satisfy a child only if its size is greater than or equal to the child's greed factor.
- 1 ≤ g.length, s.length ≤ 3 * 10⁴
- 1 ≤ g[i], s[j] ≤ 2³¹ - 1
Example
g = [1,2,3], s = [1,1]1First, both arrays are sorted: g becomes [1,2,3], s becomes [1,1]. The algorithm uses two pointers: one for children (child) and one for cookies (cookie). Starting with the smallest greed factor child (1) and the smallest cookie (1), since cookie size 1 >= greed 1, the child is content and the child pointer moves to the next child. The cookie pointer also moves forward. The next cookie (1) cannot satisfy the next child (greed 2), so only one child is content. The algorithm returns 1.
Approach
Straightforward Solution
A brute-force approach would try all assignments of cookies to children, which is computationally expensive (potentially O(n*m)). This is inefficient for large inputs.
Core Observation
To maximize the number of content children, assign the smallest cookie that can satisfy the least greedy child first. This ensures larger cookies remain available for greedier children, maximizing overall contentment.
Path to Optimal
Sorting both greed factors and cookie sizes allows a linear scan with two pointers. By always assigning the smallest sufficient cookie to the current least greedy child, the algorithm avoids wasting large cookies on less greedy children, which could prevent satisfying greedier children later.
Optimal Approach
Sort both arrays. Use two pointers to iterate through children and cookies. For each cookie, if it satisfies the current child, increment the count of content children and move to the next child. Always move to the next cookie. Return the count of content children after processing all cookies or children.
Time
O(n log n + m log m)
Sorting both arrays takes O(n log n) and O(m log m) respectively, where n and m are the lengths of g and s. The two-pointer traversal is O(n + m), which is dominated by sorting.
Space
O(1)
Sorting can be done in-place, and only a few variables are used for pointers and counters, resulting in constant auxiliary space.
Pattern Spotlight
Greedy Algorithms (Resource Allocation)
When assigning limited resources to satisfy demands, sorting both demands and resources and greedily matching the smallest sufficient resource to the smallest demand ensures maximum utilization and overall satisfaction.
Solution
| 1 | class Solution: |
| 2 | def findContentChildren(self, g: List[int], s: List[int]) -> int: |
| 3 | g.sort() |
| 4 | s.sort() |
| 5 | |
| 6 | child = cookie = 0 |
| 7 | |
| 8 | while child < len(g) and cookie < len(s): |
| 9 | if s[cookie] >= g[child]: |
| 10 | child += 1 |
| 11 | cookie += 1 |
| 12 | |
| 13 | return child |
Step-by-Step Solution
Sort Greed Factors and Cookie Sizes to Enable Efficient Matching
| 3 | g.sort() |
| 4 | s.sort() |
Objective
To arrange children and cookies in ascending order to facilitate a linear greedy matching process.
Key Insight
Sorting both arrays ensures that the algorithm can efficiently pair the smallest cookie that satisfies the smallest greed factor child, avoiding unnecessary comparisons and enabling a single pass solution.
Interview Quick-Check
Core Logic
Sorting transforms the problem into a linear scan where the smallest cookie is matched to the smallest greed factor, enabling a greedy approach.
Complexity
Sorting dominates the time complexity at O(n log n + m log m), which is acceptable given the problem constraints.
Iterate Through Children and Cookies to Assign Cookies Greedily
| 6 | child = cookie = 0 |
| 8 | while child < len(g) and cookie < len(s): |
| 9 | if s[cookie] >= g[child]: |
| 10 | child += 1 |
| 11 | cookie += 1 |
Objective
To traverse both arrays with two pointers, assigning cookies to children when possible to maximize content children count.
Key Insight
By advancing the cookie pointer regardless and only advancing the child pointer when a cookie satisfies the child's greed, the algorithm ensures no cookie is wasted and all children are considered in order of increasing greed.
Interview Quick-Check
Core Logic
The two-pointer traversal ensures each cookie is considered once, and children are satisfied in ascending order of greed, maximizing the number of content children.
State & Boundaries
The loop continues until either all children are satisfied or all cookies are considered, ensuring correctness and termination.
Common Pitfalls & Bugs
Failing to advance the cookie pointer on every iteration can cause infinite loops or missed assignments.
Return the Total Number of Content Children
| 13 | return child |
Objective
To output the count of children who have been assigned cookies that satisfy their greed.
Key Insight
The child pointer effectively counts how many children have been satisfied, so returning it directly provides the correct result.
Interview Quick-Check
Core Logic
Returning the child pointer value reflects the total number of children contented by the assigned cookies.
Line Analysis
This solution has 1 Critical line interviewers watch for.
if s[cookie] >= g[child]:Check if the current cookie can satisfy the current child's greed.
This conditional determines whether the current cookie is sufficient to content the child, which is the core decision point of the greedy algorithm.
g.sort()Sort the greed factors array in ascending order.
Sorting the greed factors allows the algorithm to consider children from least to most greedy, enabling a greedy matching strategy that maximizes content children.
s.sort()Sort the cookie sizes array in ascending order.
Sorting cookie sizes ensures that the smallest cookies are assigned first, preserving larger cookies for greedier children and enabling efficient linear matching.
cookie += 1Increment the cookie pointer to consider the next cookie.
Always moving the cookie pointer prevents infinite loops and ensures each cookie is considered exactly once, maintaining linear time complexity.
child += 1Increment the child pointer when the current child is content.
Advancing the child pointer only when a child is satisfied ensures the count of content children is accurate and that the algorithm moves on to the next child.
return childReturn the number of content children.
The child pointer represents how many children have been satisfied, so returning it directly yields the correct result.
while child < len(g) and cookie < len(s):Loop while there are children and cookies left to consider.
The loop condition ensures the algorithm stops when all children are satisfied or all cookies are exhausted, guaranteeing termination.
child = cookie = 0Initialize pointers for children and cookies to zero.
These pointers track the current child and cookie being considered, enabling a single pass through both arrays.
Test Your Understanding
Why does assigning the smallest sufficient cookie to the least greedy child guarantee the maximum number of content children?
Because giving a larger cookie to a less greedy child could waste a resource that might be necessary to satisfy a greedier child later. Assigning the smallest sufficient cookie preserves larger cookies for children with higher greed factors, maximizing total contentment.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Assign Cookies from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Assign Cookies drill