How do you solve Assign Cookies?

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.

Assign Cookies

Q: What is the time complexity of Assign Cookies?

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.

Q: What pattern does Assign Cookies use?

The Pattern: Greedy Algorithms (Resource Allocation) The Heuristic: 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.

Easy Greedy Algorithms

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

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

Output: 1

First, 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

Preview

Sorting both greed factors and cookie sizes allows a linear scan with two pointers…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort both arrays. Use two pointers to iterate through children and cookies…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

1class 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

3g.sort()
4s.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

To traverse both arrays with two pointers, assigning cookies to children when possible to maximize content children count.

Return the Total Number of Content Children

To output the count of children who have been assigned cookies that satisfy their greed.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 9 Critical

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.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does assigning the smallest sufficient cookie to the least greedy child guarantee the maximum number of content children?

See the answer with Pro.

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

or drill a free problem

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`