Leetcode – Assign Cookies Solution in Python

Spread the love

In this article, we will focus on a particular problem from Leetcode called “Assign Cookies”. We will explore multiple solutions using Python and discuss their efficiency in terms of time and space complexity.

Table of Contents

  1. Problem Statement and Understanding
  2. Approach 1: Sorting and Greedy Algorithm
  3. Approach 2: Using Priority Queues
  4. Time and Space Complexity Analysis
  5. Tips for Optimization
  6. Practical Implications
  7. Conclusion

1. Problem Statement and Understanding

Problem Statement

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example:

Input: g = [1,2,3], s = [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.

Understanding the Problem

We have an array g representing the minimum size of cookies that children will be content with and another array s representing the sizes of the cookies. We need to assign cookies to maximize the number of content children.

2. Approach 1: Sorting and Greedy Algorithm

A Greedy algorithm is used in optimization problems where we make a series of choices that lead to a globally optimum solution. In this problem, we can sort both arrays and try to assign the smallest cookie that will satisfy each child.

def findContentChildren(g, s):
    # Sort the greed factor array and the cookie size array
    g.sort()
    s.sort()
    
    # Initialize indices for greed factor array and cookie size array
    i = j = 0
    
    # Count of content children
    content_children = 0
    
    # Traverse through the greed factor array and cookie size array
    while i < len(g) and j < len(s):
        # If the size of the cookie satisfies the greed factor
        if s[j] >= g[i]:
            # Increment the content children count
            content_children += 1
            # Move on to the next child
            i += 1
        # Move on to the next cookie
        j += 1
    
    return content_children

3. Approach 2: Using Priority Queues

We can use priority queues (heaps) to solve this problem. The goal is the same, but we use heaps to always have access to the smallest element.

import heapq

def findContentChildren(g, s):
    # Convert g and s to min heaps
    heapq.heapify(g)
    heapq.heapify(s)
    
    # Count of content children
    content_children = 0
    
    # While there are elements in both heaps
    while g and s:
        # If the smallest cookie can satisfy the greediest child
        if s[0] >= g[0]:
            content_children += 1
            heapq.heappop(g)
        heapq.heappop(s)
    
    return content_children

4. Time and Space Complexity Analysis

  • Approach 1: Sorting the arrays takes O(nlogn) time. The greedy algorithm takes O(n) time as we go through each child and cookie. The space complexity is O(1) as we do not use any additional data structures.
  • Approach 2: Converting arrays to heaps takes O(n) time and assigning cookies takes O(nlogn) time. The space complexity is O(1).

5. Tips for Optimization

While the greedy algorithm seems to be the best approach, sometimes tweaking the sort algorithm or using in-place sort can save some milliseconds which is critical in coding contests.

6. Practical Implications

Understanding greedy algorithms and their applications can be widely useful not just for coding interviews but also in real-world optimization problems.

7. Conclusion

In this article, we dissected the “Assign Cookies” problem and provided multiple approaches to solving it in Python. The greedy algorithm stands out as an efficient way to solve this particular problem, but being aware of different approaches like using priority queues is beneficial.

Leave a Reply