Domain 1EasyCORE

Assign Cookies

The problem involves assigning cookies to children based on their greed factors and the sizes of available cookies. Each child has a specific greed factor `g[i]`, which represents the minimum size of a cookie that will make them content. Similarly, each cookie has a size `s[j]`. The goal is to maximize the number of content children by assigning each child at most one cookie.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy

455. Assign Cookies

Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 50.4%


Problem Breakdown

The problem involves assigning cookies to children based on their greed factors and the sizes of available cookies. Each child has a specific greed factor g[i], which represents the minimum size of a cookie that will make them content. Similarly, each cookie has a size s[j]. The goal is to maximize the number of content children by assigning each child at most one cookie.

Inputs:

  • An array g representing the greed factors of the children.
  • An array s representing the sizes of the available cookies.

Outputs:

  • An integer representing the maximum number of content children.

Implicit Constraints and Edge Cases:

  • If there are no children or no cookies, the output should be 0.
  • The arrays can contain duplicate values.
  • The values in the arrays are positive integers.

Intuition

A brute-force approach would involve checking each child against each cookie to see if it satisfies their greed factor. This approach has a time complexity of O(n * m), where n is the number of children and m is the number of cookies, which is inefficient for large inputs.

The key insight is to use a greedy algorithm. By sorting both the greed factors and the cookie sizes in non-decreasing order, we can efficiently match the smallest available cookie that satisfies each child’s greed factor. This way, we maximize the number of content children without unnecessary comparisons.

Approach

  1. Sort both arrays: Sort the greed factors g and the cookie sizes s in non-decreasing order.
  2. Initialize pointers: Use two pointers, one for iterating through the children (i) and another for iterating through the cookies (j).
  3. Match cookies to children:
    • For each child, check if the current smallest available cookie can satisfy their greed factor.
    • If it does, move both pointers forward (assign the cookie to the child) and increment the count of content children.
    • If it doesn’t, move only the pointer for cookies forward to try the next larger cookie.
  4. Stop when one array is exhausted: The process stops either when all children are considered or all cookies are used.

Complexity Analysis

  • Time Complexity: O(n log n + m log m) due to the sorting steps, where n is the number of children and m is the number of cookies.
  • Space Complexity: O(1) as we use only a constant amount of extra space for pointers and counters.

Solution

def findContentChildren(g: List[int], s: List[int]) -> int:
    # Sort both arrays in non-decreasing order
    g.sort()
    s.sort()
    
    i, j = 0, 0  # Pointers for children and cookies respectively
    content_children = 0
    
    # Iterate through both arrays
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:  # If the current cookie can satisfy the current child
            content_children += 1  # Increment the count of content children
            i += 1  # Move to the next child
        j += 1  # Move to the next cookie
    
    return content_children

Edge Cases Handled

  • No Children or No Cookies: If either g or s is empty, the function returns 0 immediately after sorting.
  • Duplicate Values: The sorting handles duplicates naturally, and the greedy approach ensures that each child gets at most one cookie.
  • Large Input Sizes: The solution efficiently handles large inputs due to its linearithmic time complexity.