Problem statement

You want to give cookies to children. Child i is content only with a cookie of size at least g[i], their greed factor. Cookie j has size s[j], and each child may receive at most one cookie.

Return the maximum number of children you can content.

Example 1

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: Only the least greedy child can be satisfied.

Example 2

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

Example 3

Input: g = [5], s = [1,2,3]
Output: 0

Constraints

• 1 <= g.length, s.length <= 40
• 1 <= g[i], s[j] <= 1000

Hints for Assign Cookies

1. Hint 1

   Sort both lists and walk them together with two pointers.

2. Hint 2

   Always give the smallest cookie that will actually content the least greedy remaining child.

3. Hint 3

   Wasting a large cookie on a small child can never help — the exchange argument makes greedy optimal.

How to solve Assign Cookies

Sort both lists and walk them with two pointers, giving the smallest cookie that satisfies the least greedy remaining child.

Approach

1. Sort g and s.
2. With i over children and j over cookies: if s[j] >= g[i], content child i (advance i); always advance j.
3. Return i.

Why it works

If an optimal assignment gives a larger cookie to the least greedy child while a smaller sufficient one exists, swapping them keeps every child content — so the smallest sufficient cookie is never a bad choice, and a cookie too small for the least greedy child is useless to everyone.

Complexity

• Time — O(n log n + m log m)
• Space — O(1) beyond the sorts

Pitfalls

• Advance the cookie pointer even when the cookie is skipped, or the loop stalls.

Reference solution

Python

def findContentChildren(g, s) -> int:
    greed = sorted(g)
    sizes = sorted(s)
    i = j = 0
    while i < len(greed) and j < len(sizes):
        if sizes[j] >= greed[i]:
            i += 1
        j += 1
    return i

Java

public static int findContentChildren(int[] g, int[] s) {
    int[] greed = g.clone();
    int[] sizes = s.clone();
    Arrays.sort(greed);
    Arrays.sort(sizes);
    int i = 0, j = 0;
    while (i < greed.length && j < sizes.length) {
        if (sizes[j] >= greed[i]) i++;
        j++;
    }
    return i;
}

C++

int findContentChildren(vector<int>& g, vector<int>& s) {
    vector<int> greed = g;
    vector<int> sizes = s;
    sort(greed.begin(), greed.end());
    sort(sizes.begin(), sizes.end());
    int i = 0, j = 0;
    while (i < (int) greed.size() && j < (int) sizes.size()) {
        if (sizes[j] >= greed[i]) i++;
        j++;
    }
    return i;
}

JavaScript

var findContentChildren = function(g, s) {
    const greed = g.slice().sort(function(a, b) { return a - b; });
    const sizes = s.slice().sort(function(a, b) { return a - b; });
    let i = 0, j = 0;
    while (i < greed.length && j < sizes.length) {
        if (sizes[j] >= greed[i]) i++;
        j++;
    }
    return i;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy