LeetCode Problem 455

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Greedy, Sorting

Solution

LeetCode 455, Assign Cookies

Problem Understanding

This problem asks us to maximize the number of children who can be satisfied with the available cookies. Each child has a greed factor, and each cookie has a size. A child becomes content only if they receive a cookie whose size is greater than or equal to their greed factor.

The input consists of two integer arrays:

• g, where g[i] represents the minimum cookie size required for child i
• s, where s[j] represents the size of cookie j

Each child can receive at most one cookie, and each cookie can only be assigned once. The goal is to determine the maximum number of children that can be satisfied.

The important part of the problem is that we are not trying to maximize the total cookie usage or minimize waste. We only care about maximizing the count of satisfied children.

The constraints are important:

• Both arrays can contain up to 3 * 10^4 elements
• Cookie sizes and greed factors can be very large integers
• The input size is large enough that inefficient nested matching approaches may become too slow

Because the arrays can each contain tens of thousands of elements, we should expect that an O(n log n) solution is appropriate, while a naive O(n * m) solution may become inefficient in the worst case.

There are several important edge cases:

• There may be no cookies at all
• There may be fewer cookies than children
• There may be more cookies than children
• Some cookies may be too small for every child
• Multiple children or cookies may have the same values
• The arrays are not guaranteed to be sorted

A correct implementation must handle all of these cases consistently.

Approaches

Brute Force Approach

A straightforward approach is to try assigning cookies to children one by one using a nested loop.

For every child, we could scan through all available cookies and select the smallest unused cookie that satisfies the child's greed factor. After assigning a cookie, we mark it as used so it cannot be reused.

This approach produces the correct answer because it explicitly checks all possible assignments and ensures that each cookie is used at most once.

However, the performance is poor. If there are n children and m cookies, then for each child we may scan the entire cookie array. This leads to O(n * m) time complexity.

With both arrays potentially having size 3 * 10^4, the worst case could involve around 9 * 10^8 operations, which is too slow.

Optimal Greedy Approach

The key observation is that we should use the smallest possible cookie that can satisfy a child.

If we waste a large cookie on a child with small greed, we may later fail to satisfy a greedier child who actually needed the larger cookie.

This naturally suggests a greedy strategy:

1. Sort both arrays
2. Always try to satisfy the least greedy remaining child using the smallest sufficient remaining cookie

By sorting both arrays, we can efficiently move through them using two pointers.

If the current cookie is large enough for the current child, we assign it and move both pointers forward.

If the cookie is too small, then that cookie cannot satisfy the current child or any future child, because future children will have equal or greater greed. Therefore, we safely discard the cookie and move to the next one.

This greedy decision is optimal because it preserves larger cookies for greedier children.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(m)	Try every cookie for every child
Optimal	O(n log n + m log m)	O(1) or O(log n) depending on sorting	Sort both arrays and use two pointers

Algorithm Walkthrough

1. Sort the g array in ascending order.

This allows us to process children from least greedy to most greedy. Smaller greed requirements are easier to satisfy, so we handle them first. 2. Sort the s array in ascending order.

This allows us to process cookies from smallest to largest. We want to avoid wasting large cookies when a smaller one would work. 3. Initialize two pointers.

One pointer tracks the current child, and the other tracks the current cookie.

child_index = 0
cookie_index = 0

4. Iterate while both pointers remain within bounds.

At each step, compare the current cookie size with the current child's greed factor. 5. If the cookie can satisfy the child:

s[cookie_index] >= g[child_index]

then assign the cookie to the child.

Increment both pointers because:

• that child is now satisfied
• that cookie has been used

6. If the cookie is too small:

s[cookie_index] < g[child_index]

then discard the cookie.

Increment only the cookie pointer because:

• the cookie cannot satisfy this child
• it also cannot satisfy any future child since future greed values are even larger

7. Continue until either:

• all children are satisfied, or
• all cookies are exhausted

8. The number of satisfied children equals the child pointer value.

Why it works

The algorithm maintains the invariant that we always assign the smallest possible cookie capable of satisfying the current least greedy child.

This greedy choice is optimal because using a larger cookie unnecessarily could reduce our ability to satisfy greedier children later. By always matching the smallest sufficient cookie, we maximize future flexibility.

Sorting ensures that once a cookie is too small for a child, it will also be too small for every later child, allowing us to safely discard it.

Python Solution

from typing import List

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        child_index = 0
        cookie_index = 0

        while child_index < len(g) and cookie_index < len(s):
            if s[cookie_index] >= g[child_index]:
                child_index += 1

            cookie_index += 1

        return child_index

The implementation begins by sorting both arrays. This is the foundation of the greedy strategy because it allows us to process both children and cookies in increasing order.

The variable child_index tracks how many children have been satisfied so far. The variable cookie_index tracks which cookie we are currently considering.

Inside the loop, we compare the current cookie against the current child's greed factor.

If the cookie is large enough, we satisfy the child and move to the next child. Regardless of whether the cookie succeeds or fails, we always move to the next cookie because each cookie can only be used once.

At the end, child_index represents the total number of satisfied children.

The implementation is concise because the greedy logic eliminates the need for additional data structures or bookkeeping.

Go Solution

package main

import "sort"

func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)

	childIndex := 0
	cookieIndex := 0

	for childIndex < len(g) && cookieIndex < len(s) {
		if s[cookieIndex] >= g[childIndex] {
			childIndex++
		}

		cookieIndex++
	}

	return childIndex
}

The Go implementation follows the same logic as the Python solution.

The main difference is that Go uses sort.Ints() from the standard library to sort slices in place.

Go slices naturally handle empty inputs, so no special handling is required for empty cookie arrays.

There is also no integer overflow concern because we only compare values and increment indices.

Worked Examples

Example 1

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

After sorting:

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

Step	child_index	cookie_index	Current Child	Current Cookie	Action
1	0	0	1	1	Cookie satisfies child
2	1	1	2	1	Cookie too small

After step 1:

• Child with greed 1 is satisfied
• Move both pointers

After step 2:

• Cookie size 1 cannot satisfy greed 2
• Discard cookie

Now all cookies are exhausted.

Final result:

1

Example 2

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

After sorting:

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

Step	child_index	cookie_index	Current Child	Current Cookie	Action
1	0	0	1	1	Cookie satisfies child
2	1	1	2	2	Cookie satisfies child

After step 1:

• Child with greed 1 receives cookie 1

After step 2:

• Child with greed 2 receives cookie 2

All children are satisfied.

Final result:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m log m)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation

The main cost comes from sorting the two arrays.

After sorting, the two pointer traversal is linear because each pointer moves forward at most once through its array.

The sorting implementations may use small amounts of auxiliary stack space internally, depending on the language runtime.

Test Cases

solution = Solution()

# Provided example 1
assert solution.findContentChildren([1, 2, 3], [1, 1]) == 1

# Provided example 2
assert solution.findContentChildren([1, 2], [1, 2, 3]) == 2

# No cookies available
assert solution.findContentChildren([1, 2, 3], []) == 0

# More cookies than children
assert solution.findContentChildren([1, 2], [1, 2, 3, 4]) == 2

# All cookies too small
assert solution.findContentChildren([5, 6, 7], [1, 2, 3]) == 0

# Exact matches
assert solution.findContentChildren([1, 2, 3], [1, 2, 3]) == 3

# Duplicate greed factors
assert solution.findContentChildren([2, 2, 2], [2, 2]) == 2

# Duplicate cookie sizes
assert solution.findContentChildren([1, 2, 3], [2, 2, 2]) == 2

# Single child satisfied
assert solution.findContentChildren([1], [1]) == 1

# Single child not satisfied
assert solution.findContentChildren([2], [1]) == 0

# Large cookie wasted if greedy is incorrect
assert solution.findContentChildren([1, 3], [1, 2]) == 1

# Unsorted input arrays
assert solution.findContentChildren([3, 1, 2], [2, 1, 3]) == 3

Test	Why
[1,2,3], [1,1]	Basic example where not all children can be satisfied
[1,2], [1,2,3]	Basic example where all children are satisfied
[1,2,3], []	Validates handling of empty cookie array
[1,2], [1,2,3,4]	Ensures extra cookies do not affect correctness
[5,6,7], [1,2,3]	Verifies behavior when no cookie is sufficient
[1,2,3], [1,2,3]	Exact one to one matching
[2,2,2], [2,2]	Duplicate greed factors
[1,2,3], [2,2,2]	Duplicate cookie sizes
[1], [1]	Smallest successful input
[2], [1]	Smallest unsuccessful input
[1,3], [1,2]	Validates greedy matching behavior
[3,1,2], [2,1,3]	Confirms sorting is required

Edge Cases

One important edge case occurs when there are no cookies available. In this scenario, no child can possibly be satisfied regardless of greed factors. A buggy implementation might attempt to access elements from an empty cookie array and crash. The two pointer loop naturally handles this because the loop condition immediately fails when len(s) == 0.

Another important edge case involves cookies that are all too small. For example:

g = [5, 6, 7]
s = [1, 2, 3]

A naive implementation might repeatedly retry impossible matches inefficiently. The sorted greedy approach handles this correctly because once a cookie is too small for the current child, it is discarded immediately.

A third important edge case involves duplicate values. Multiple children may have identical greed factors, and multiple cookies may have identical sizes. Some incorrect implementations accidentally reuse cookies or mishandle repeated values. This implementation avoids those problems because each cookie pointer advances exactly once, guaranteeing that every cookie is used at most once.

Another subtle case occurs when input arrays are unsorted. The greedy strategy only works correctly after sorting. Without sorting, assigning cookies in arbitrary order may waste larger cookies on less greedy children and reduce the total number of satisfied children. Sorting ensures that we always make locally optimal decisions that lead to a globally optimal result.