Problem Description

You need to distribute cookies to children in a way that maximizes the number of satisfied children.

Each child has a greed factor g[i], which represents the minimum cookie size that will make that child content. Each cookie has a size s[j]. A cookie j can be given to child i only if the cookie size is at least as large as the child's greed factor: s[j] >= g[i].

Rules:

• Each child can receive at most one cookie
• Each cookie can be given to at most one child
• A child is content only if they receive a cookie that meets or exceeds their greed factor

Goal: Find the maximum number of children that can be made content with the available cookies.

Example:

• If you have children with greed factors g = [1, 2, 3] and cookies with sizes s = [1, 1]
• You can satisfy at most 1 child (give a cookie of size 1 to the child with greed factor 1)
• The child with greed factor 2 and 3 cannot be satisfied with the remaining cookies

The problem asks you to return an integer representing the maximum number of children that can be satisfied.

Intuition

The key insight is to think about this problem greedily. We want to maximize the number of satisfied children, so we should avoid "wasting" large cookies on children with small greed factors.

Consider this scenario: if we have a child with greed factor 1 and another with greed factor 5, and we have cookies of size 1 and 6. If we give the size-6 cookie to the child with greed factor 1, we've wasted that large cookie - the child with greed factor 5 will remain unsatisfied. Instead, if we give the size-1 cookie to the child with greed factor 1, both children can be satisfied.

This leads us to a greedy strategy: always try to satisfy the child with the smallest greed factor using the smallest cookie that can satisfy them. This ensures we don't waste larger cookies on children who could be satisfied with smaller ones.

To implement this strategy efficiently:

1. Sort both arrays so we can process children from smallest to largest greed factor
2. For each child (starting from the one with smallest greed), find the smallest cookie that can satisfy them
3. Once a cookie is used, move to the next available cookie
4. If we run out of cookies or can't find a suitable cookie for a child, we've found our maximum

This greedy approach works because satisfying a child with a smaller greed factor first will never prevent us from achieving a better solution. We're essentially making the locally optimal choice at each step (use the smallest viable cookie for the current child), which leads to the globally optimal solution (maximum number of satisfied children).

Solution Approach

The implementation uses a two-pointer technique combined with sorting to efficiently match cookies to children.

Step 1: Sort both arrays

g.sort()
s.sort()

This allows us to process children from smallest to largest greed factor and cookies from smallest to largest size.

Step 2: Initialize pointers

• Use index i to iterate through children array g (implicitly through enumerate)
• Use pointer j to track the current position in cookies array s
• Start j = 0 at the beginning of the cookies array

Step 3: Main matching logic For each child g[i], we need to find the smallest cookie that can satisfy them:

while j < len(s) and s[j] < g[i]:
    j += 1

This loop skips all cookies that are too small for the current child. We keep moving j forward until we find a cookie large enough (s[j] >= g[i]) or run out of cookies.

Step 4: Check if cookie is available

if j >= len(s):
    return i

If j goes out of bounds, it means we've exhausted all cookies. The number of children satisfied so far is i (since we're using 0-based indexing).

Step 5: Assign cookie and move forward

j += 1

If we found a suitable cookie, we assign it to the current child and move j forward to the next cookie (since each cookie can only be used once).

Step 6: Return result

return len(g)

If we successfully iterate through all children without running out of cookies, it means all children have been satisfied.

Time Complexity: O(n log n + m log m) where n is the number of children and m is the number of cookies, due to sorting both arrays. The traversal itself is O(n + m).

Space Complexity: O(1) if we don't count the space used by sorting (which depends on the implementation).

Example Walkthrough

Let's walk through a concrete example to see how the greedy two-pointer approach works.

Given:

• Children's greed factors: g = [3, 1, 5, 2]
• Cookie sizes: s = [1, 2, 3]

Step 1: Sort both arrays

• Sorted children: g = [1, 2, 3, 5]
• Sorted cookies: s = [1, 2, 3]

Step 2: Initialize pointers

• Start with j = 0 (pointing to first cookie)
• We'll iterate through children using index i

Step 3: Process each child

Child 0 (greed = 1):

• Check cookie at j=0: size 1 ≥ greed 1? ✓ Yes!
• Assign cookie of size 1 to this child
• Move j to 1 (next cookie)
• Children satisfied: 1

Child 1 (greed = 2):

• Check cookie at j=1: size 2 ≥ greed 2? ✓ Yes!
• Assign cookie of size 2 to this child
• Move j to 2 (next cookie)
• Children satisfied: 2

Child 2 (greed = 3):

• Check cookie at j=2: size 3 ≥ greed 3? ✓ Yes!
• Assign cookie of size 3 to this child
• Move j to 3 (now out of cookies)
• Children satisfied: 3

Child 3 (greed = 5):

• j=3 is out of bounds (no more cookies)
• Return current count: 3

Result: Maximum of 3 children can be satisfied

Notice how the greedy approach ensures we don't waste large cookies on children with small greed factors. By matching the smallest available cookie to each child, we maximize the total number of satisfied children.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m + n × log n), where m is the length of array g (children) and n is the length of array s (cookies).

• Sorting array g takes O(m × log m) time
• Sorting array s takes O(n × log n) time
• The iteration through array g with the while loop takes O(m + n) time in the worst case, since each element in both arrays is visited at most once
• The dominant operations are the sorting steps, so the overall time complexity is O(m × log m + n × log n)

Space Complexity: O(log m + log n)

• The sorting operations use O(log m) space for array g and O(log n) space for array s due to the recursive call stack in the sorting algorithm (typically quicksort or heapsort in Python's Timsort)
• The algorithm uses only a constant amount of extra variables (i, j, x), which is O(1)
• Therefore, the total space complexity is O(log m + log n)

Common Pitfalls

1. Not Moving the Cookie Pointer After Assignment

A critical mistake is forgetting to increment the cookie pointer after assigning a cookie to a child. This would cause the same cookie to be potentially assigned to multiple children.

Incorrect Implementation:

for child_index, greed_factor in enumerate(g):
    while cookie_index < len(s) and s[cookie_index] < g[child_index]:
        cookie_index += 1
  
    if cookie_index >= len(s):
        return child_index
  
    # MISTAKE: Forgot to increment cookie_index
    # This cookie could be "reused" for the next child

Solution: Always increment cookie_index after a successful match:

cookie_index += 1  # Move to next cookie after assignment

2. Using the Wrong Variable in the While Loop Condition

Another common error is mixing up array indices, particularly using greed_factor instead of g[child_index] or vice versa.

Incorrect Implementation:

for child_index, greed_factor in enumerate(g):
    # MISTAKE: Using greed_factor but comparing with g[child_index]
    while cookie_index < len(s) and s[cookie_index] < g[child_index]:
        cookie_index += 1
    # Should consistently use either greed_factor or g[child_index]

Solution: Be consistent with variable usage:

# Option 1: Use greed_factor everywhere
while cookie_index < len(s) and s[cookie_index] < greed_factor:
    cookie_index += 1

# Option 2: Use g[child_index] everywhere
while cookie_index < len(s) and s[cookie_index] < g[child_index]:
    cookie_index += 1

3. Forgetting to Sort the Arrays

The greedy algorithm only works correctly when both arrays are sorted. Without sorting, you might miss valid cookie-child pairs.

Incorrect Implementation:

def findContentChildren(self, g: List[int], s: List[int]) -> int:
    # MISTAKE: Forgot to sort the arrays
    cookie_index = 0
  
    for child_index, greed_factor in enumerate(g):
        # This won't work correctly with unsorted arrays
        ...

Solution: Always sort both arrays at the beginning:

g.sort()
s.sort()

4. Incorrect Return Value Calculation

When returning early (when cookies are exhausted), using the wrong index or forgetting that indices are 0-based can lead to off-by-one errors.

Incorrect Implementation:

if cookie_index >= len(s):
    return child_index + 1  # MISTAKE: Adding 1 incorrectly

Solution: Return child_index directly, which represents the number of children satisfied so far (due to 0-based indexing):

if cookie_index >= len(s):
    return child_index  # Correct: this is the count of satisfied children