Assign Cookies

Easy

Assign Cookies

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum possible lengths of the `greed` and `sizes` arrays?
Can the values in the `greed` and `sizes` arrays be zero or negative?
If no children can be made content, should I return 0?
Are there any constraints on the range of values within the `greed` and `sizes` arrays?
If there are multiple valid assignments that maximize content children, is any one acceptable?

Brute Force Solution

Approach

We want to find the maximum number of children we can satisfy with cookies. The brute force way means trying every possible combination of assigning cookies to children to see which gives us the most satisfied kids.

Here's how the algorithm would work step-by-step:

Consider the first child and try giving them the first cookie.
If the cookie is big enough for the child, mark the child as satisfied.
Then consider the first child and try giving them the second cookie instead of the first cookie, and so on.
Keep going through every cookie and see if it satisfies the first child.
Once you've tried every cookie for the first child, move on to the second child.
Again, try every cookie for the second child, and see if it satisfies them, but remember we can't use cookies that have already been assigned to a child.
Repeat this process for every child, trying every possible cookie that hasn't already been given away.
Keep track of the total number of satisfied children for each possible combination of cookie assignments.
Finally, compare all these combinations, and pick the one that results in the maximum number of satisfied children.

Code Implementation

def assign_cookies_brute_force(child_greed_factors, cookie_sizes):
    maximum_satisfied_children = 0

    def solve(child_index, assigned_cookies, satisfied_children_count):
        nonlocal maximum_satisfied_children

        # Base case: all children have been considered
        if child_index == len(child_greed_factors):
            maximum_satisfied_children = max(maximum_satisfied_children, satisfied_children_count)
            return

        # Explore all possible cookie assignments for the current child
        for cookie_index in range(len(cookie_sizes)): 
            if cookie_index not in assigned_cookies:
                # Check if the cookie satisfies the current child.
                if cookie_sizes[cookie_index] >= child_greed_factors[child_index]:

                    # Assign the cookie and recursively explore next child.
                    assigned_cookies.add(cookie_index)

                    solve(child_index + 1, assigned_cookies, satisfied_children_count + 1)

                    assigned_cookies.remove(cookie_index)

        # If no cookie satisfies the child, move to the next child.
        # The child is not satisfied, check what happens with next child
        solve(child_index + 1, assigned_cookies, satisfied_children_count)

    solve(0, set(), 0)

    return maximum_satisfied_children

Big(O) Analysis

Time Complexity

O(m! * n) – The algorithm explores every possible assignment of cookies to children. Let 'm' be the number of children and 'n' be the number of cookies. In the worst-case, the algorithm effectively generates all permutations of assigning cookies to children, which takes O(m!) time because it has to explore all possible ways to assign. For each of these permutations, checking if the size of each cookie is adequate for the child is O(n). Thus, the overall time complexity is approximately O(m! * n).

Space Complexity

O(2^M) – The described brute force solution explores all possible combinations of assigning cookies to children. In the worst case, where M is the number of cookies, the algorithm implicitly maintains a call stack to explore each combination. Each level of the recursion can branch out to try assigning each of the M cookies. This leads to a branching factor of close to M at each level, and a maximum recursion depth related to the number of children. Thus, the number of potential branches (combinations) can grow exponentially. In the worst-case scenario it can lead to a space complexity proportional to 2^M to manage these combinations, primarily due to the call stack. The number of satisfied children is being tracked, so auxiliary space is needed. Even with a small number of children and cookies the combinations quickly become massive.

Optimal Solution

Approach

The goal is to satisfy as many children as possible with cookies. We want to be efficient and not waste any cookies. The best way to do this is to give the smallest possible cookie to the least greedy child, and move upwards from there.

Here's how the algorithm would work step-by-step:

First, sort both the children's greediness and the cookies by size, so we can easily find the smallest of each.
Then, start with the least greedy child and the smallest cookie.
If the smallest cookie can satisfy that child's greediness, give the cookie to the child, and move on to the next child and the next cookie.
If the smallest cookie isn't big enough, then throw that cookie away and try the next bigger cookie for the same child.
Keep doing this until we run out of children or cookies. The number of children we successfully gave cookies to is the answer.

Code Implementation

def assign_cookies(greed_factors, cookie_sizes): 
    greed_factors.sort()
    cookie_sizes.sort()

    child_index = 0
    cookie_index = 0
    number_of_happy_children = 0

    while child_index < len(greed_factors) and cookie_index < len(cookie_sizes):
        # We want to satisfy the least greedy child with the smallest cookie.
        if cookie_sizes[cookie_index] >= greed_factors[child_index]:

            number_of_happy_children += 1
            child_index += 1

        # If the current cookie is too small, move to the next bigger cookie.
        cookie_index += 1

    return number_of_happy_children

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting both the children's greediness (g) and the cookies' sizes (s). Sorting algorithms like merge sort or quicksort have a time complexity of O(n log n), where n represents the size of the input array. After sorting, we iterate through both arrays using two pointers, which takes O(m+k) time, where m is the number of children and k is the number of cookies. Since m and k are bounded by the size of the input and the sorting complexity dominates, the overall time complexity is O(n log n).

Space Complexity

O(1) – The provided solution sorts both the children's greediness and the cookies. Depending on the sorting algorithm used, this might require auxiliary space. However, if an in-place sorting algorithm like heapsort is employed, the sorting step uses O(1) auxiliary space. The algorithm then iterates using a constant number of pointer variables to track the current child and cookie being considered. No additional data structures are created that scale with the input size. Therefore, the overall space complexity is O(1).

Edge Cases

Case	How to Handle
Both greed and sizes arrays are empty	Return 0 since there are no children or cookies.
Greed array is empty but sizes array is not	Return 0 since there are no children to satisfy.
Sizes array is empty but greed array is not	Return 0 since there are no cookies to give.
All children have very large greed factors and all cookies are small	Return 0 since no children can be satisfied.
All cookies are very large and all children have small greed factors	Return the number of children since all can be satisfied.
Greed and sizes arrays contain duplicate values	Sorting both arrays ensures the greedy approach can still find the optimal solution by matching smallest greed to smallest cookie.
Arrays are very large (performance considerations)	The sorting algorithm must be efficient (e.g., O(n log n)) to handle large arrays within time limits.
Integer overflow if greed factors or sizes are extremely large	The comparison of greed factors and sizes should be done using a data type that prevents overflow (e.g., long in Java or C++ if necessary), but the problem likely constrains the inputs so that normal integers can be used.