LeetCode 455: Assign Cookies

Problem Restatement

We are given two arrays:

g
s

The array g stores the greed factor of each child.

The array s stores the size of each cookie.

A child i is content if we give them one cookie j such that:

s[j] >= g[i]

Each child can get at most one cookie.

Each cookie can be used at most once.

We need to return the maximum number of content children. The official problem states that each child has a minimum cookie size they need, and our goal is to maximize the number of content children.

Input and Output

Function shape:

def findContentChildren(g: list[int], s: list[int]) -> int:
    ...

Examples

Example 1:

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

The first child needs a cookie of size at least 1.

We can give them one cookie of size 1.

The second child needs a cookie of size at least 2, but the remaining cookie has size 1.

So only one child can be content.

Answer:

1

Example 2:

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

Give cookie 1 to the child with greed 1.

Give cookie 2 to the child with greed 2.

Answer:

2

Example 3:

g = [10, 9, 8, 7]
s = [5, 6, 7, 8]

After sorting:

g = [7, 8, 9, 10]
s = [5, 6, 7, 8]

Cookie 5 and cookie 6 are too small for greed 7.

Cookie 7 satisfies greed 7.

Cookie 8 satisfies greed 8.

Answer:

2

First Thought: Try Every Assignment

A direct idea is to try assigning cookies to children in many possible ways.

For each child, we could search for a cookie that satisfies them.

But the choice matters.

For example:

g = [1, 2]
s = [2, 1]

If we give cookie 2 to the child with greed 1, then cookie 1 cannot satisfy the child with greed 2.

Only one child becomes content.

But the better assignment is:

greed 1 gets cookie 1
greed 2 gets cookie 2

Then two children become content.

So we need a systematic way to avoid wasting large cookies on children who can accept smaller cookies.

Problem With Brute Force

Trying all assignments is expensive.

Each cookie can go to different children, and the number of possible matchings grows quickly.

Even a simpler repeated-search approach can cost:

O(len(g) * len(s))

That may still be more work than needed.

A greedy sorted approach gives a cleaner solution.

Key Insight

To maximize the number of content children, satisfy the least greedy children first.

Also, for each child, use the smallest cookie that can satisfy them.

This preserves larger cookies for children who need them.

So we sort both arrays:

g.sort()
s.sort()

Then we use two pointers:

child = 0
cookie = 0

The current child is the least greedy remaining child.

The current cookie is the smallest remaining cookie.

There are two cases.

If the cookie is large enough:

s[cookie] >= g[child]

we assign it and move to the next child and next cookie.

If the cookie is too small:

s[cookie] < g[child]

then it cannot satisfy this child or any later child, since later children have equal or larger greed. So we discard this cookie and try the next larger cookie.

Algorithm

Sort g.

Sort s.

Initialize:

child = 0
cookie = 0

While both pointers are in range:

1. If the current cookie can satisfy the current child, assign it.
2. Move to the next child.
3. Always move to the next cookie, because the current cookie is either used or too small.

At the end, child is the number of content children.

Walkthrough

Use:

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

Both arrays are already sorted.

Start:

child = 0
cookie = 0

Compare:

g[0] = 1
s[0] = 1

Cookie size 1 satisfies greed 1.

So:

child = 1
cookie = 1

Now compare:

g[1] = 2
s[1] = 1

Cookie size 1 is too small.

Discard the cookie:

cookie = 2

Now there are no cookies left.

The answer is:

child = 1

Correctness

After sorting, children are processed from smallest greed to largest greed, and cookies are processed from smallest size to largest size.

When the current cookie is too small for the current child, it cannot satisfy any remaining child because every remaining child has greed at least as large as the current child’s greed. Discarding that cookie cannot reduce the best possible answer.

When the current cookie can satisfy the current child, assigning it is safe because this child has the smallest greed among all remaining children, and this cookie is the smallest available cookie that we have reached. Using this cookie now preserves all larger cookies for children with larger greed.

Each step either discards a useless cookie or makes one child content using the smallest suitable cookie. Therefore, the algorithm makes every locally safe choice needed to maximize the total number of content children.

Complexity

Let:

m = len(g)
n = len(s)

The sorting implementation may use extra internal memory depending on the language.

Implementation

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        g.sort()
        s.sort()

        child = 0
        cookie = 0

        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                child += 1

            cookie += 1

        return child

Code Explanation

First we sort both arrays:

g.sort()
s.sort()

This lets us match small greed values with small cookie sizes.

Then:

child = 0
cookie = 0

child points to the least greedy child who has not been satisfied yet.

cookie points to the smallest unused cookie.

The loop continues while there is still at least one child and one cookie to consider:

while child < len(g) and cookie < len(s):

If the current cookie can satisfy the current child:

if s[cookie] >= g[child]:
    child += 1

then one more child is content, and we move to the next child.

In every loop, we move to the next cookie:

cookie += 1

because the current cookie has either been assigned or proved too small.

Finally:

return child

returns how many children were satisfied.

Testing

def run_tests():
    s = Solution()

    assert s.findContentChildren([1, 2, 3], [1, 1]) == 1
    assert s.findContentChildren([1, 2], [1, 2, 3]) == 2
    assert s.findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]) == 2
    assert s.findContentChildren([], [1, 2, 3]) == 0
    assert s.findContentChildren([1, 2, 3], []) == 0
    assert s.findContentChildren([1, 1, 1], [1, 1]) == 2
    assert s.findContentChildren([2, 3, 4], [1, 1, 1]) == 0

    print("all tests passed")

run_tests()

Test meaning: