Problem 455

(Last updated: )

Question 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 $\texttt{i}$ has a greed factor $\texttt{g[i]}$, which is the minimum size of a cookie that the child will be content with; and each cookie $\texttt{j}$ has a size $\texttt{s[j]}$. If $\texttt{s[j]} \geq \texttt{g[i]}$, we can assign the cookie $\texttt{j}$ to the child $\texttt{i}$, and the child $\texttt{i}$ will be content. Your goal is to maximize the number of your content children and output the maximum number.

Solution:

Main idea:

There is probably a smarter way to do this, but the greedy approach got the problem accepted (with a decent runtime) - so I will outline the greedy approach here: Give the cookie with the smallest size, to the kid having the smallest greed level who is still able to accept that cookie. This can be achieved as follows:

  • Sort both arrays $\texttt{s}$ and $\texttt{g}$.
  • For each cookie in $\texttt{s}$, find the first child in $\texttt{g}$ that this cookie would satisfy.
  • Once a match is made, pop both the cookie and the child from $\texttt{s}$ and $\texttt{g}$ respectively.
    • Add 1 to a satisfaction $\texttt{counter}$.
  • If no such child exists, pop the cookie out of $\texttt{s}$.
  • Continue this way until $\texttt{s}$ is empty.

Alternatively, instead of using the $\texttt{pop()}$ function, it might be slightly faster to have a $\texttt{cookie_index}$ and a $\texttt{kid_index}$ that act like pointers moving across $\texttt{s}$ and $\texttt{g}$ respectively.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findContentChildren(self, g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    kid_index = 0
    cookie_index = 0
    count = 0

    while(cookie_index < len(s) and kid_index < len(g)):
        if(s[cookie_index]< g[kid_index]):
            cookie_index+=1
        else:
            count+=1
            cookie_index+=1
            kid_index+=1
    return count


Comments:

Time complexity: O($\texttt{max(len(g), len(s))}$)

At the time of submission, the above solution passes leetcode submission cases in 132ms, beating 96.37% of users. It uses 19.2MB of memory, beating 10.05% of users.