Start by sorting both the children's greed factors and cookie sizes. Use a two-pointer approach to scan through the arrays: assign the smallest cookie that satisfies each child, moving pointers carefully to maintain the invariant that no child is skipped unnecessarily. This ensures the maximum number of content children is counted efficiently while adhering strictly to the problem's greedy, two-pointer pattern.
Problem Statement
You are given an array g where g[i] represents the greed factor of the i-th child and an array s where s[j] represents the size of the j-th cookie. Each child can receive at most one cookie, and a child is content only if they receive a cookie with size greater than or equal to their greed factor. Your task is to determine the maximum number of content children.
Implement a function that, given g and s, outputs an integer representing the maximum number of children who can be content. For example, with g = [1,2,3] and s = [1,1], only one child can be satisfied, while g = [1,2] and s = [1,2,3] allows all children to be content.
Examples
Example 1
Input: g = [1,2,3], s = [1,1]
Output: 1
You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.
Example 2
Input: g = [1,2], s = [1,2,3]
Output: 2
You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.
Constraints
- 1 <= g.length <= 3 * 104
- 0 <= s.length <= 3 * 104
- 1 <= g[i], s[j] <= 231 - 1
Solution Approach
Sort Both Arrays
Sort the greed factor array g and the cookie size array s in ascending order to enable a straightforward two-pointer scan.
Use Two Pointers
Initialize two pointers at the start of g and s. For each child, move the cookie pointer until a cookie large enough is found. If found, increment both pointers and count the child as content. Otherwise, move only the child pointer.
Maintain Invariant and Count
Ensure that each assignment preserves the invariant that unassigned children are checked with the smallest remaining cookies. This guarantees the greedy choice is valid and the maximum content children are calculated.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O (n \cdot \log n + m \cdot \log m) |
| Space | O(m + n) |
Time complexity is O(n log n + m log m) due to sorting both arrays, where n is the number of children and m is the number of cookies. Two-pointer scanning is O(n + m), and space complexity is O(n + m) for storing sorted arrays.
What Interviewers Usually Probe
- Does the candidate sort arrays before scanning?
- Are two pointers used efficiently to assign cookies?
- Is the invariant maintained so no child is skipped incorrectly?
Common Pitfalls or Variants
Common pitfalls
- Failing to sort arrays before scanning, leading to suboptimal assignments.
- Not maintaining two-pointer invariant, resulting in skipped children or incorrect counts.
- Incorrectly incrementing pointers, causing double assignment or missed content children.
Follow-up variants
- Reverse the problem: minimize cookies used to satisfy all children.
- Allow multiple cookies per child, requiring modification of two-pointer logic.
- Children or cookies are extremely large, testing time and space efficiency under constraints.
How GhostInterview Helps
- Provides a guided step-by-step assignment using the two-pointer invariant method.
- Highlights pitfalls like pointer mismanagement and unsorted arrays to prevent incorrect greedy results.
- Demonstrates variant adjustments for different greedy constraints and maximal content counting.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Assign Cookies?
The problem uses a two-pointer scanning pattern combined with greedy sorting to assign the smallest sufficient cookie to each child.
Why do we sort both arrays before assigning cookies?
Sorting ensures that the smallest available cookie is matched with the least greedy child first, maintaining the greedy invariant.
How do two pointers work in this problem?
One pointer tracks children and the other tracks cookies; pointers increment based on whether the current cookie satisfies the current child.
Can a child receive more than one cookie?
No, each child can receive at most one cookie, which is central to maintaining the two-pointer invariant.
What are common mistakes when implementing Assign Cookies?
Common mistakes include not sorting arrays, mismanaging pointer increments, and failing to count content children accurately.
Need direct help with Assign Cookies instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Assign Cookies from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the shortest unsorted continuous subarray that, if sorted, would sort the entire array.
Open problem page#611 Valid Triangle NumberCount all triplets in an integer array that satisfy the triangle inequality to form valid triangles efficiently using sorting and binary search.
Open problem page#826 Most Profit Assigning WorkAssign workers to jobs maximizing total profit using difficulty, profit, and worker arrays efficiently with binary search pattern.
Open problem page