How do you solve Assign Cookies on LeetCode?

Assign Cookies (LeetCode #455) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n + m log m) time complexity and O(1) space complexity. Key insight: Sorting both arrays allows for a more efficient matching process.

What is the brute force solution for Assign Cookies?

The brute force approach for Assign Cookies is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we check every possible combination of assigning cookies to children. This means we will try to assign each cookie to each child and see if it satisfies their greed factor. While this is straightforward, it can be inefficient. The optimal Optimal Solution approach improves this to O(n log n + m log m).

What algorithm or data structure is used to solve Assign Cookies?

Assign Cookies uses the following concepts: Array, Two Pointers, Greedy, Sorting. The recommended patterns to study are: Greedy Algorithm, Sorting.

What are the interview tips for Assign Cookies?

Always clarify the problem and constraints before diving into coding. Discuss your thought process and potential approaches with the interviewer. Be mindful of edge cases, such as when there are no cookies or no children.

What are common mistakes when solving Assign Cookies?

Not sorting the arrays before trying to match children with cookies. Failing to account for the situation where cookies run out before all children are satisfied.

#455

Assign Cookies

Easy

ArrayTwo PointersGreedySortingGreedy AlgorithmSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n + m log m)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n + m log m)Space O(1)

The optimal approach uses sorting and a greedy strategy. By sorting both the greed factors and cookie sizes, we can efficiently assign the smallest available cookie that satisfies each child's greed, maximizing the number of content children.

⚙️

Algorithm

4 steps

1Step 1: Sort both the greed factors array g and the cookie sizes array s.
2Step 2: Initialize two pointers, one for children (i) and one for cookies (j).
3Step 3: Iterate through both arrays; if the cookie at j satisfies the greed of child at i, increment both pointers (content child found). Otherwise, just increment the cookie pointer (try next cookie).
4Step 4: Continue until either all children are satisfied or all cookies are used.

solution.py17 lines

1# Full working Python code
2
3def findContentChildren(g, s):
4    g.sort()
5    s.sort()
6    content_children = 0
7    i = 0  # Pointer for children
8    j = 0  # Pointer for cookies
9    while i < len(g) and j < len(s):
10        if s[j] >= g[i]:
11            content_children += 1
12            i += 1  # Move to next child
13        j += 1  # Move to next cookie
14    return content_children
15
16# Example usage
17print(findContentChildren([1, 2, 3], [1, 1]))  # Output: 1

ℹ

Complexity note: The sorting step takes O(n log n) for the greed factors and O(m log m) for the cookie sizes, where n is the number of children and m is the number of cookies. The subsequent traversal is O(n + m).

1Sorting both arrays allows for a more efficient matching process.
2Using a greedy approach ensures that we always try to satisfy the least greedy child first with the smallest available cookie.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.