Assign Cookies

Difficulty: Easy | Acceptance: 54.90% | Paid: No Topics: Array, Two Pointers, Greedy, Sorting

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of content children and output the maximum number.

• Examples
• Constraints
• Greedy with Two Pointers
• Greedy with Binary Search
• Brute Force

Examples

Example 1

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, their sizes are 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
Explanation: You have 2 children and 2 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 * 10^4
- 0 <= s.length <= 3 * 10^4
- 1 <= g[i], s[j] <= 2^31 - 1

Greedy with Two Pointers

Intuition Sort both arrays and use two pointers to match the smallest satisfying cookie to each child, maximizing the number of satisfied children.

Steps

• Sort both greed factors and cookie sizes arrays
• Use two pointers, one for children and one for cookies
• If current cookie satisfies current child, increment both pointers and count
• Otherwise, move to the next larger cookie
• Return the count of satisfied children

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        g.sort()
        s.sort()
        child = cookie = count = 0
        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                count += 1
                child += 1
            cookie += 1
        return count

Complexity

• Time: O(n log n + m log m)
• Space: O(1) or O(n + m) depending on sorting implementation
• Notes: Optimal solution with simple two-pointer technique

Greedy with Binary Search

Intuition Sort both arrays and for each child, use binary search to find the smallest unused cookie that satisfies their greed factor.

Steps

• Sort both arrays
• Use a boolean array to track used cookies
• For each child, binary search for the smallest unused cookie that satisfies them
• Mark the cookie as used and increment count if found
• Return the count of satisfied children

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        g.sort()
        s.sort()
        used = [False] * len(s)
        count = 0
        
        for greed in g:
            left, right = 0, len(s) - 1
            found = -1
            while left <= right:
                mid = (left + right) // 2
                if s[mid] >= greed and not used[mid]:
                    found = mid
                    right = mid - 1
                elif s[mid] < greed:
                    left = mid + 1
                else:
                    right = mid - 1
            
            if found != -1:
                used[found] = True
                count += 1
        
        return count

Complexity

• Time: O(n log n + m log m + n log m)
• Space: O(m) for tracking used cookies
• Notes: More complex than two-pointer approach with worse constant factors

Brute Force

Intuition Try all possible assignments of cookies to children and find the maximum number of satisfied children.

Steps

• Generate all possible assignments of cookies to children
• For each assignment, count how many children are satisfied
• Return the maximum count found

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        from itertools import permutations
        
        max_count = 0
        n = len(s)
        
        for i in range(n + 1):
            for cookies in permutations(s, i):
                count = 0
                used = [False] * len(g)
                for cookie in cookies:
                    for j in range(len(g)):
                        if not used[j] and cookie >= g[j]:
                            used[j] = True
                            count += 1
                            break
                max_count = max(max_count, count)
        
        return max_count

Complexity

• Time: O(m! * n * m)
• Space: O(m) for storing permutations
• Notes: Only for educational purposes, will TLE on large inputs