We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Assign Cookies

Number: 455

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Microsoft, Bloomberg, Accenture, Apple, Adobe

Problem Description

You are given an array of integers g representing the greed factors of children and an array of integers s representing the sizes of cookies. A child will be content if they receive a cookie with a size greater than or equal to their greed factor. The goal is to maximize the number of content children by distributing the cookies, where each child can receive at most one cookie.

Key Insights

  • Sort both the greed factor array and the cookie sizes array.
  • Use a two-pointer approach to iterate through both arrays.
  • If the current cookie can satisfy the current child's greed, assign it and move to the next child.
  • Continue until either all children are checked or all cookies are used.

Space and Time Complexity

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). Space Complexity: O(1) if sorting is done in-place, otherwise O(n + m) if extra space is used to copy lists.

Solution

The approach is based on greedy allocation. By sorting the children based on their greed factors and sorting the cookies by size, we can efficiently match the smallest available cookie that is sufficient for a given child. The two-pointer technique helps in traversing both arrays simultaneously, ensuring that we don’t waste a potentially larger cookie on a child with lower greed if a smaller cookie would suffice. This strategy maximizes the number of content children.

Code Solutions

# Python solution for assigning cookies

def findContentChildren(g, s):
    # Sort greed factors and cookie sizes
    g.sort()  # Sorting children by greed factor
    s.sort()  # Sorting cookies by size
    
    child = 0  # Pointer for children
    cookie = 0  # Pointer for cookies
    
    # Iterate until we exhaust either cookies or children
    while child < len(g) and cookie < len(s):
        # If current cookie satisfies current child's greed factor
        if s[cookie] >= g[child]:
            child += 1  # Assign cookie to child, move to next child
        cookie += 1  # Move to next cookie regardless of assignment
    
    return child  # Number of content children

# Example usage:
print(findContentChildren([1,2,3], [1,1]))  # Expected output: 1
print(findContentChildren([1,2], [1,2,3]))  # Expected output: 2
← Back to All Questions