What is the brute force approach and complexity for Assign Cookies?

Backtrack over the children: each one gets no cookie, or any free cookie that is big enough with time complexity O((M + 1)^N) and space complexity O(N + M).

What is the optimal approach and complexity for Assign Cookies?

Sort both lists. Walk the cookies from smallest, and give each one to the least greedy waiting child if it fits with optimal time complexity O(N log N + M log M) and space complexity O(1).

How do you identify the pattern for Assign Cookies?

Look for key signals in the prompt: "each child gets at most one cookie" indicates Each child and each cookie can be used at most once, so this is a one-to-one pairing.; "greed factor" indicates A minimum: a cookie works only if its size is at least the greed.; "maximize the number of content children" indicates Count the pairs, and use the small cookies on the children who can take them..

Assign Cookies

Easy·LeetCode #455Basic Anchor

LeetCode

Jump:

30-Second Mental ModelResource assignment: sort both, match the smallest that works

Complexity:O((M + 1)^N)→O(N log N + M log M)

Key Insight

Sort the children by greed and the cookies by size. Walk the cookies from smallest to biggest, with a pointer to the least greedy child who has no cookie yet. If the cookie is big enough for that child, give it to them and move the pointer on. If it is too small, skip it. The pointer's final position is the answer.

Core Validity Invariant

A cookie can make the waiting child happy only if the cookie is at least as big as that child's greed: s[cookie] ≥ g[child].

Problem

You are handing out cookies to some children. Each child has a greed number: the smallest cookie size that makes them happy. Each cookie has a size.

A child is happy only with a cookie that is at least as big as their greed number. Each child can get at most one cookie, and each cookie can go to at most one child.

Hand out the cookies so that as many children as possible are happy. Return that number.

Input

g, the greed numbers of the children, and s, the sizes of the cookies. s can be empty.

Output

One integer: the largest number of children that can be happy.

Example 1

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

Output: 1

Both cookies are size 1, so only the child with greed 1 can be happy. The other two need a cookie of size 2 or more.

Example 2

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

Output: 2

Give the greed-1 child a cookie of size 1, and the greed-2 child a cookie of size 2. Both are happy, and the size-3 cookie is left over.

Constraints

• 1 ≤ g.length ≤ 3 · 10^4
• 0 ≤ s.length ≤ 3 · 10^4
• 1 ≤ g[i], s[j] ≤ 2^31 − 1

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What is the goal: to make the most children happy, or to use up the most cookies?
2.
If I give a big cookie to a child who only needed a small one, what might I be blocking for a greedier child?
3.
If a cookie is too small for the least greedy child, can it still help anyone?
4.
Does the order of the children matter here? Does the order of the cookies matter?
5.
For g = [1, 2, 3] and s = [1, 1], is the answer the number of cookies? Why or why not?

Brute force approach

Idea

Go through the children in order. For each child, try giving no cookie, and try each unused cookie that is big enough. Keep the largest count of happy children over all these choices.

Thinking process

1
The real question is which child gets which cookie, so I try the options one child at a time.
2
Take g = [1, 2, 3] and s = [1, 1]. Child 1 can take either size-1 cookie, or nothing. For each choice, the next children try the cookies that are still free.
3
Keep a used flag for each cookie, so no cookie is handed out twice.
4
Each child has up to M + 1 options, so the number of paths grows very fast.

Code & Implementation

brute.cpp

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        vector<bool> used(s.size(), false);
        return solve(0, g, s, used);
    }

private:
    // The most happy children from child i onward, given which cookies are already taken.
    int solve(int i, vector<int>& g, vector<int>& s, vector<bool>& used) {
        if (i == (int)g.size()) return 0;

        // Choice 1: child i gets no cookie.
        int best = solve(i + 1, g, s, used);

        // Choice 2: child i gets each free cookie that is big enough.
        for (int j = 0; j < (int)s.size(); j++) {
            if (used[j] || s[j] < g[i]) continue;
            used[j] = true;
            best = max(best, 1 + solve(i + 1, g, s, used));
            used[j] = false;   // undo, so the next cookie can be tried
        }
        return best;
    }
};

Complexity

Time O((M + 1)^N)Space O(N + M)

N is the number of children and M the number of cookies. Each child has at most M + 1 choices (one of the cookies, or none), so there can be about (M + 1)^N paths. The used check cuts some of them, but the worst case is still exponential. The recursion is N levels deep, and used has M flags.

Better approach

Why brute force is slow

Each child scans all M cookies. Most of them are either too small for that child, or already taken.

What repeated work are we doing?

The children are visited from least greedy to most greedy. A cookie too small for one child is also too small for every child after them. The scan still checks it again for each child.

What information can we reuse?

Sort the cookies as well. Then the smallest cookie that fits is at a pointer, and the pointer only moves forward. That is the optimal walk.

New approach

Idea

Sort the children from least greedy to most greedy. For each child, scan every cookie and pick the smallest free cookie that is big enough. If there is one, the child is happy.

Thinking process

1
The brute force tries every hand-out. A simple rule should be enough.
2
The least greedy child should get the smallest cookie that works for them. That leaves the bigger cookies for the greedier children.
3
Check it on g = [1, 2, 3] and s = [1, 1]: child 1 takes a size-1 cookie. Child 2 looks for a cookie of size 2 or more and finds none. Child 3 finds none too. Answer 1, the same as the brute force.
4
The rule is right, but each child scans every cookie to find the smallest one that fits.

Code & Implementation

better.cpp

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());   // least greedy child first
        vector<bool> used(s.size(), false);
        int happy = 0;
        for (int greed : g) {
            // Scan every cookie for the smallest free one that is big enough.
            int pick = -1;
            for (int j = 0; j < (int)s.size(); j++)
                if (!used[j] && s[j] >= greed && (pick == -1 || s[j] < s[pick])) pick = j;
            if (pick != -1) {
                used[pick] = true;
                happy++;
            }
        }
        return happy;
    }
};

Complexity

Time O(N · M)Space O(M)

For each of the N children, the scan looks at all M cookies. That is the main cost. Sorting the children adds O(N log N) on top. The used flags take O(M) space.

Optimized approach

Idea

Start from brute force

Brute force tries every hand-out. The better version still scans every cookie for every child. Once both lists are sorted, finding each child's cookie is just one step forward along the cookie list.

Find the repeated work

A cookie that is too small for one child is checked again for every later child. Children are visited from least greedy to most greedy, so a cookie that is too small now stays too small. We can skip it once and never look at it again.

Define the state — what variables do I need?

child: Index of the least greedy child who is still waiting for a cookie. Every child before it is happy.
cookie: Index of the cookie we are looking at now. Cookies are sorted from smallest to biggest.

Define validity

A cookie can make the waiting child happy only if the cookie is at least as big as that child's greed: s[cookie] ≥ g[child].

Define the transitions — when does each pointer move, and why is it safe?

s[cookie] ≥ g[child]

child++ (this child is happy). Then cookie++.

This is the smallest cookie that works for the waiting child. A bigger cookie would be wasted on them, and it is more useful for a greedier child later.

s[cookie] < g[child]

cookie++ (skip it).

The cookie is too small for the least greedy child still waiting. Every child after them is at least as greedy, so no one who is waiting can use this cookie.

What does the current window add to the answer?

Each time child moves forward, one more child is happy. Children are only counted once, so the final value of child is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());   // least greedy child first
        sort(s.begin(), s.end());   // smallest cookie first

        int child = 0;  // the least greedy child who is still waiting
        for (int cookie = 0; cookie < (int)s.size() && child < (int)g.size(); cookie++) {
            // Big enough for the waiting child: give it and move on.
            // Too small: it is too small for every waiting child (they are all at least as greedy), so skip it.
            if (s[cookie] >= g[child]) child++;
        }
        return child;   // children 0 … child − 1 are happy
    }
};

Complexity

Time O(N log N + M log M)Space O(1)

Sorting the children costs O(N log N) and sorting the cookies costs O(M log M). The walk over the cookies is one pass, O(M). Extra space is O(1), not counting the sort's own stack.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Backtrack over the children: each one gets no cookie, or any free cookie that is big enough	O((M + 1)^N)	O(N + M)
Better	Take the least greedy child first, and scan all cookies for the smallest free one that fits	O(N · M)	O(M)
Optimal	Sort both lists. Walk the cookies from smallest, and give each one to the least greedy waiting child if it fits	O(N log N + M log M)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“each child gets at most one cookie”Each child and each cookie can be used at most once, so this is a one-to-one pairing.
“greed factor”A minimum: a cookie works only if its size is at least the greed.
“maximize the number of content children”Count the pairs, and use the small cookies on the children who can take them.

Pair each child with a cookie of size ≥ greed+each item used at most once+maximise the number of pairs→Resource assignment: sort both, match the smallest that works

This is the anchor of the assignment sub-pattern. The rule is give the smallest cookie that is big enough, so the big cookies stay free for greedy children. The leftover cookies are simply not counted. Advantage Shuffle is different: every value there must be used, so a losing pair still has to be paired with something.

Don't make this mistake

Pattern confusion: giving the least greedy child the biggest cookie

✗ for each child (least greedy first): give the BIGGEST cookie that is big enough

✓ for each child (least greedy first): give the SMALLEST cookie that is big enough

The big cookies are needed by the greedy children. On g = [3, 1, 5, 2] and s = [4, 1, 1], the wrong rule gives the greed-1 child the 4. After that, the greed-2 child can only use a 1, so nobody else is happy. Result: 1. The right rule gives the greed-1 child a 1 and the greed-2 child the 4. Result: 2.

Using > instead of ≥

✗ if (s[j] > g[i])

✓ if (s[j] >= g[i])

A cookie that is exactly the child's greed makes them happy. With g = [1] and s = [1], the > check says 0 children are happy, but the answer is 1.

Returning the smaller list length

✗ return min(g.size(), s.size());

✓ return the child pointer after the walk

Counting cookies is not the same as counting happy children. With g = [1, 2, 3] and s = [1, 1], the min is 2. But the second cookie is too small for the greed-2 child, so the answer is 1.

Sorting only one list

✗ sort(g.begin(), g.end()); // s is still in the given order

✓ sort(g.begin(), g.end()); sort(s.begin(), s.end());

The walk needs both lists in order. With g = [1, 2] and s = [3, 1], the cookie 3 comes first and makes the greed-1 child happy. Then the cookie 1 is too small for the greed-2 child. Result: 1. With both sorted, the cookie 1 goes to the greed-1 child and the cookie 3 to the greed-2 child. Result: 2.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture