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
grepresenting the greed factors of the children. - An array
srepresenting 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
- Sort both arrays: Sort the greed factors
gand the cookie sizessin non-decreasing order. - Initialize pointers: Use two pointers, one for iterating through the children (
i) and another for iterating through the cookies (j). - 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.
- 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
nis the number of children andmis 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
gorsis 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.