Assign Cookies problem

Assign cookies problem is a popular coding interview question which is mostly solved using greedy algorithm. Here, you will be given a list of children/siblings and a list of cookies with their sizes. Your goal is to maximize the number of children/siblings you can content with your cookies and output the number. If you want to know how to solve this problem, this article is for you.

Table of contents:

1. Problem Statement
2. Greedy Algorithm Approach
3. Examine few examples
4. Solving the Problem
5. Time and Space Complexity

Problem statement

Given two arrays of integers, the first array represent the greedy factor of the siblings, while the other one represent the cookies. Maximize the number of content siblings and output the maximum number.

Let's examing below scenario.

You are an elder brother with quiet number of younger ones who love to take cookies. As an awesome elder brother you are, you got them pack of cookies which contain boxes of cookies with different sizes. Whereas, Each of your siblings has a size of cookies they can satisfy with. In other words, Each of your siblings can only be contented with a certain size of cookies. You should maximize the number of siblings you can satisfy with the available cookies. But, only one box of cookies should be given to one person.

To solve this problem, you need to assign each sibling a box of cookie such that the sibling's greedy factor is greater than or equal to the size of the cookies. Greedy algorithm is most suitable approach for this kind of problem. Let's learn about greedy algorithm approach and solve the problem with it.

Greedy Algorithm Approach

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result. It works for cases where minimization or maximization leads to the required solution

This algorithm may not produce the best result for all the problems. It's because it always goes for the local best choice to produce the global best result.

Characteristics of Greedy Algorithm

Before adopting greedy approach to solve a problem, it must follow the underline characteristics.

• There is an ordered list of resources(cookies, value, cost, etc).
• Maximum of all the resources (max cookies, max cost) are taken

Basic structure of Greedy Algorithm

• Declare an empty result = 0
• Make a greedy choice to select, if the choice is feasible, add to the result
• Return the result

Examine few examples

Example 1

Giving a greedy vectors or array of integers denoted by g = [1, 2, 3] and array of cookies represented by s = [1, 1], find a maximum number of content children.
Here, we assume that the length of greedy factor represent the number of children we have and g[i] is a greedy factor that child at index i can be contented with.
We have three (3) siblings and two (2) boxes of cookies, each sibling has a greedy factor of 1, 2, 3 respectively.

The size of the two cookies are 1 and 1 which means the child with 1 greedy factor can only be satisfied, hence, the output will be 1.

Example 1

Inputs are g = [1,2], s = [1,2,3]. This means we have two (2) siblings with a greedy factors of 1 and 2 and three (3) cookies with size of 1, 2, 3.

Since the size of cookies are big enough to gratify the two siblings, The output of the above example will be 2.

Solving the Problem

We are going to implement the solution using Python3 and greedy algorithm approach.

def findContentSibling(g: list[int], s: list[int]) -> int:
    """Find the maximum number of content siblings

    Args:
        g (list[int]) - greedy factors of the siblings
        s (list[int]) - size of the cookies

   Return:
       (int) - maximum number of contented siblings
    """"
    g.sort()
    s.sort()

    res = gi = si = 0

    while gi < len(g) and si < len(s):
        if s[si] >= g[gi]:
            res += 1
            si, gi = si + 1, gi + 1
        else:
            si += 1
    return res

    if __name__ == '__main__':
        g1 = [1, 2, 3]
        s1 = [1, 1]
        res1 = findContentSibling(g1, s1)
        print(res1)

        g2 = [1, 2]
        s2 =[1, 2, 3]
        res2 = findContentSibling(g2, s2)
        print(res1)

output1:
    1

output2:
    2

Since the goal of the problem is to maximize the number of contented siblings the following steps were taken:

• We sorted both the greedy factor, and the size of the cookies. This will allow us to start from the sibling with a less greedy factor.
• We initiliazed res - which is going to hold the final result, gi and si - which represent greedy factor index and size of cookies index respectively and they are all assigned to zero (0).
• We ran a while loop which is going to continue running until end of either of array g or s. This will allow us to visit every greedy factor and size of cookies possible.
• Inside the loop, we checked whether a size of cookies could satisfy a sibling greedy factor or not. If true, we increment the res variable by 1 otherwise, we increment the size of cookies so we could test the greedy factor against the next size of cookies.
• Finally, we return the res variable which holds the maximum number of contented siblings.

Time and Space complexity

Time complexity: O(nlogn + mlogm + max(m, n))
Space complexity: O(max(logm + logn))
Where n stands for g and n stands for s.

Here, we used python sort function which use Timsort algorithm under the hood. The time complexity of Timsort algorithm is O(nlogn). Therefore, the two sorts is O(nlogn + mlogm) and the loop inside the function runs O(max(n, m)).

The space complexity O(max(logm + logn)), since the built-in sort in python is Timsort.

The auxiliary space complexity is O(1).