Assign Cookies LeetCode

Key takeaways
The problem statement of Assign Cookies LeetCode is to maximize the number of happy children by distributing cookies based on greed levels and cookie sizes.
Sort the greed factors of the children, g, and the sizes of the cookies, s, in ascending order.
Use a two-pointer technique to iterate through both sorted arrays; match cookies to children by checking if the cookie size meets or exceeds the child's greed.
The time complexity of Assign Cookies problem is $O(nlogn+mlogm)$ for sorting and iteration.
The space complexity of Assign Cookies problem is due to sorting.

The Assign Cookies problem is a popular coding challenge often encountered in technical interviews at major tech companies like Meta, Google, and Microsoft. It's famous for testing candidates' ability to think algorithmically and use data structures effectively, especially arrays and sorting methods. In this problem, you're given a list of children's greed levels and a set of cookies with different sizes. Your task is to distribute the cookies in such a way that you maximize the number of children who are happy. This problem helps candidates practice optimizing resource allocation and problem-solving strategies, making it a valuable addition to coding practice sessions.

Problem statement

Imagine being the favorite teacher among the children. You have some cookies, and you want to distribute them to the children in such a way that each child gets at most one cookie. The distribution of cookies will go as follows:

Each child, i, has a greed factor, g[i], which means this is the smallest size of a cookie that will make them happy.
Each cookie, j, has a size s[j]. If the size of a cookie s[j] is equal to or bigger than a child's greed factor g[i], i.e., s[j] $\geq$ g[i], then that cookie can be given to that child to make them happy.

Given the arrays of greed factor (g) and the size of cookies (s), your task is to maximize the number of children that will be happy and return the maximum number.

Constraints

$1 \leq$ g.length $\leq 3 \times 10^3$
$0 \leq$ s.length $\leq 3 \times 10^3$
$1 \leq$ g[i], s[j] $\leq 2^{31} - 1$

Let’s take a look at a few examples to get a better understanding of the problem statement:

Solution

We start with sorting the greed factors of the children, g, and the sizes of the cookies, s, in ascending order. Sorting helps in efficiently matching the smallest available cookie that meets or exceeds each child's greed factor. We then use two pointers, one for each array, to iterate through them. Starting with the smallest greed factor and the smallest cookie, we attempt to make each child happy. We update the pointers as follows:

If a cookie size can make a child happy as per their greed factor, i.e., s[j] $\geq$ g[i], we move to the next child and the next cookie.
If a cookie size is too small, we only move to the next cookie and not the child. This is to proceed towards a cookie that is large enough.

By the end of the iteration, we count how many children have been satisfied. This approach ensures that the maximum number of children are satisfied with the available cookies, leveraging the efficiency of the greedy strategy.

Here's how the algorithm works:

Sort the arrays, g and s, in ascending order.
Initialize child_i to 0 (this pointer will iterate over the greed factors of children), and cookie_i to 0 (this pointer will iterate over the sizes of cookies).
Iterate as long as child_i is less than the length of g and cookie_i is less than the length of s.
- Check if the current cookie size can make the current child happy:
  - If the size of the current cookie s[cookie_i] is greater than or equal to the greed factor of the current child g[child_i], increment child_i by one (move to the next child).
- Move to the next cookie by incrementing cookie_i.
Return the value of child_i which represents the maximum number of happy children.

Now, let’s look at the following illustration to get a better understanding of the solution:

def max_happy_children(g, s):
    
    # Sort both arrays
    g.sort()
    s.sort()
    
    child_i = 0  # Pointer for children
    cookie_i = 0  # Pointer for cookies
    
    # Iterate through both arrays
    while child_i < len(g) and cookie_i < len(s):
        
        # If the cookie can make the child happy
        if s[cookie_i] >= g[child_i]:
            # Move to the next child
            child_i += 1  
        
        # Move to the next cookie in any case
        cookie_i += 1
        
    # The number of happy children
    return child_i  
# Driver code
def main():
    inputs = [
        ([1, 2, 3], [1, 1]),
        ([1, 2], [1, 2, 3]),
        ([1, 3, 2, 2], [2, 2, 2, 2]),
        ([5, 10, 2], [1, 2, 3, 8]),
        ([1, 1, 1], [1, 2, 3]),
        ([10, 9, 8, 7], [5, 6, 7, 8, 9])
    ]
    for i, (g, s) in enumerate(inputs, start=1):
        print(f"{i}. Greed factors: {g}")
        print(f"   Cookie sizes: {s}")
        result = max_happy_children(g, s)
        print(f"   Number of happy children: {result}")
        print("-" * 100, "\n")
if __name__ == "__main__":
    main()

Assign Cookies

Now that we have a solution for this LeetCode problem, let’s analyze its time and space complexity to understand how efficiently it scales with larger inputs.

Time complexity

Sorting the greed factors array, g, and the cookie sizes array, s, each takes $O(n \log n)$ and $O(m \log m)$ respectively, where $n$ is the length of g and $m$ is the length of s. Iterating through both arrays once takes $O(n+m)$ . Because the $O(n \log n)$ and $O(m \log m)$ terms dominate the linear terms $O(n+m)$ , the overall time complexity is $O(n \log n + m \log m)$ .

Space complexity

The space complexity of this solution is primarily determined by the space used for sorting. Sorting algorithms usually have a space complexity of $O(n)$ for auxiliary space. Therefore, the overall space complexity of this solution is $O(n + m)$ , considering the space needed for sorting both arrays.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Assign Cookies LeetCode

Problem statement

Knowledge test

Solution

Time complexity

Space complexity