#455

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Assign Cookies

Maximize content children by assigning at most one cookie per child using two-pointer scanning and greedy sorting techniques.

array two pointers greedy sorting

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.

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.

terminal

Solution

Solution 1: Sorting + Two Pointers

According to the problem description, we should prioritize giving cookies to children with smaller appetites, so as to satisfy as many children as possible.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        j = 0
        for i, x in enumerate(g):
            while j < len(s) and s[j] < g[i]:
                j += 1
            if j >= len(s):
                return i
            j += 1
        return len(g)

Continue Practicing

#581 shortest unsorted continuous subarray #611 valid triangle number #826 most profit assigning work