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 your content children and output the maximum number.

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, 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
Explanation: 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 * 10^4
  • 0 <= s.length <= 3 * 10^4
  • 1 <= g[i], s[j] <= 2^31 - 1

Thinking Process

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 your content children and output the maximum number.

  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Sort + greedy (this problem) O(n log n) O(1) Interval scheduling, assignment
Local greedy choice O(n) O(1) Jump game, gas station
Greedy + heap O(n log n) O(n) Merge streams, room allocation
Exchange argument O(n) O(1) Prove greedy choice is safe

Solution

Solution 1: Two Pointers with Conditional Advancement

class Solution:
    def findContentChildren(self, g, s):
        g.sort()
        s.sort()
        count = 0
        i = 0
        j = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                count += 1
                i += 1
                j += 1
                return count

Solution Explanation

Approach: Sort + greedy (this problem)

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

How the code works:

  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?

Walkthrough — input g = [1,2,3], s = [1,1], expected 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.

Time: - Sorting: O(g log g + s log s) where g = g , s = s · Space: O(1) - only using a few variables (excluding input arrays) 
class Solution:
    def findContentChildren(self, g, s):
        g.sort()
        s.sort()
        num_of_children, num_of_cookies = len(g), len(s)
        count = 0
        j = 0
        for i in range(num_of_children):
            while j < num_of_cookies and g[i] > s[j]:
                j += 1
            if j < num_of_cookies:
                count += 1
                j += 1
            else:
                break
        return count

Algorithm Explanation:

Solution 1:

  1. Sort Arrays (Lines 4-5):
    • Sort g in ascending order (children’s greed factors)
    • Sort s in ascending order (cookie sizes)
  2. Two Pointers Matching (Lines 6-14):
    • Initialize: i for children, j for cookies, count for assignments
    • While both arrays have elements:
      • If cookie satisfies child: s[j] >= g[i]
        • Increment count
        • Move to next child (i++)
        • Move to next cookie (j++)
      • Else: Cookie too small, skip it (j++)

Solution 2:

  1. Sort Arrays (Lines 4-5): Same as Solution 1

  2. For Each Child (Lines 7-13):

    • Skip small cookies: Use while loop to skip cookies smaller than child’s greed
    • Check bounds: Ensure j < numOfCookies after skipping
    • Assign if valid: If cookie found, increment count
    • Advance both: Move to next child and cookie

Example Walkthrough:

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

After sorting:

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

Solution 1 Execution:

Initial: i=0, j=0, count=0

Step 1: s[0]=1 >= g[0]=1 ✓
  count=1, i=1, j=1

Step 2: s[1]=1 < g[1]=2 ✗
  j=2 (out of bounds)

Result: count=1

Solution 2 Execution:

Initial: i=0, j=0, count=0

i=0: g[0]=1
  while: j=0, s[0]=1 >= 1, no skip
  j=0 < 2 ✓, count=1
  i=1, j=1

i=1: g[1]=2
  while: j=1, s[1]=1 < 2, j=2 (out of bounds)
  j=2 >= 2 ✗, no assignment

Result: count=1

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

After sorting:

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

Solution 1 Execution:

Initial: i=0, j=0, count=0

Step 1: s[0]=1 >= g[0]=1 ✓
  count=1, i=1, j=1

Step 2: s[1]=2 >= g[1]=2 ✓
  count=2, i=2 (out of bounds)

Result: count=2

Solution 2 Execution:

Initial: i=0, j=0, count=0

i=0: g[0]=1
  while: j=0, s[0]=1 >= 1, no skip
  j=0 < 3 ✓, count=1
  i=1, j=1

i=1: g[1]=2
  while: j=1, s[1]=2 >= 2, no skip
  j=1 < 3 ✓, count=2
  i=2 (out of bounds)

Result: count=2

Algorithm Breakdown

Why Greedy Works

The greedy strategy is optimal because:

  1. Smallest First: Assign smallest cookie to smallest child maximizes remaining options
  2. No Regret: If we skip a cookie for a child, we can’t use it later (each child gets at most one)
  3. Optimal Substructure: After assigning a cookie, the subproblem (remaining children and cookies) is independent

Why Sorting is Necessary

Without sorting, we might:

  • Assign a large cookie to a child with small greed factor
  • Miss opportunities to satisfy more children
  • Need to check all combinations (O(n²))

With sorting:

  • Process in order (smallest to largest)
  • Greedy choice is optimal
  • Linear time matching

Comparison of Solutions

Solution 1:

  • Advancement: Cookie pointer advances in both branches
  • Logic: Clear if-else structure
  • Efficiency: Both pointers advance optimally

Solution 2:

  • Advancement: Cookie pointer skips multiple small cookies at once
  • Logic: Uses while loop to skip cookies
  • Efficiency: Same time complexity, slightly different style

Both solutions have the same time complexity and produce the same result.

Time & Space Complexity

  • Time Complexity:
    • Sorting: O(g log g + s log s) where g = g , s = s
    • Matching: O(g + s) - each element visited at most once
    • Total: O(g log g + s log s)
  • Space Complexity: O(1) - only using a few variables (excluding input arrays)

Key Points

  1. Greedy Algorithm: Always make locally optimal choice
  2. Sorting: Essential for greedy approach to work
  3. Two Pointers: Efficient matching technique
  4. Optimal: Greedy strategy maximizes number of content children
  5. Simple: Straightforward implementation

Edge Cases

  1. No cookies: s = [] → return 0
  2. No children: g = [] → return 0
  3. All cookies too small: g = [5,6,7], s = [1,2,3] → return 0
  4. All children satisfied: g = [1,2], s = [3,4,5] → return 2
  5. Single child, single cookie: g = [1], s = [1] → return 1

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Array, Greedy, Sorting, Two Pointers, Easy

Key Takeaways

  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?

References

Template Reference