# LeetCode 455: Assign Cookies

## Problem Restatement

We are given two arrays:

```python
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:

```python
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

| Item | Meaning |
|---|---|
| Input | `g`, greed factors of children |
| Input | `s`, cookie sizes |
| Output | Maximum number of content children |
| Rule | A cookie satisfies a child if its size is at least the child's greed |
| Limit | Each child and each cookie can be used once |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
1
```

Example 2:

```python
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:

```python
2
```

Example 3:

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

After sorting:

```python
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:

```python
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:

```python
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:

```python
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:

```python
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:

```python
g.sort()
s.sort()
```

Then we use two pointers:

```python
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:

```python
s[cookie] >= g[child]
```

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

If the cookie is too small:

```python
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:

```python
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:

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

Both arrays are already sorted.

Start:

```python
child = 0
cookie = 0
```

Compare:

```python
g[0] = 1
s[0] = 1
```

Cookie size `1` satisfies greed `1`.

So:

```python
child = 1
cookie = 1
```

Now compare:

```python
g[1] = 2
s[1] = 1
```

Cookie size `1` is too small.

Discard the cookie:

```python
cookie = 2
```

Now there are no cookies left.

The answer is:

```python
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:

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m log m + n log n)` | We sort both arrays |
| Space | `O(1)` extra | The two-pointer scan uses constant extra space |

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

## Implementation

```python
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:

```python
g.sort()
s.sort()
```

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

Then:

```python
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:

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

If the current cookie can satisfy the current child:

```python
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:

```python
cookie += 1
```

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

Finally:

```python
return child
```

returns how many children were satisfied.

## Testing

```python
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:

| Test | Why |
|---|---|
| `[1,2,3]`, `[1,1]` | Standard example with too few large cookies |
| `[1,2]`, `[1,2,3]` | More cookies than children |
| `[10,9,8,7]`, `[5,6,7,8]` | Requires sorting |
| Empty children | No child can be content |
| Empty cookies | No cookie can be assigned |
| Duplicate greed values | Counts repeated children correctly |
| All cookies too small | Answer should be `0` |