Assign Cookies

GREEDY · EASY

Builds on Day 27: Greedy Algorithms

Read that lesson first for the general “make the locally-best choice, don’t look back” idea. The optimal solution here is also a sorted two-pointer scan, the same shape as Day 4’s Two-Pointer Pattern — worth a glance if pointer convergence over sorted arrays is still new.

The problem

You have some cookies to hand out. Each child i has a greed factor g[i] — the smallest cookie size that child will actually be happy with. Each cookie j has a size s[j]. A cookie can go to a child only if s[j] >= g[i], and each child gets at most one cookie. Given g and s, return the maximum number of children you can make content.

LeetCode: Assign Cookies

Solution 1: Brute force — for each child, scan every cookie for the best fit

Don’t sort anything. Just walk the children in whatever order they arrived, and for each one, scan the entire cookie array looking for the smallest cookie that’s still big enough (a “best fit” search, not just the first fit you happen to run into — grabbing the first sufficient cookie you see can waste a cookie that a later, pickier child actually needed, so it has to be the smallest sufficient one). Mark it used and move to the next child. Every child re-scans up to every cookie, so this is O(n·m).

g = [5, 2, 3] · s = [3, 4, 1] — best-fit rescan, no sorting

Press Play or Step to begin.

Step 0 / 16

▶ Play↺ Reset

The code

function assignCookiesBruteForce(g, s) {
  const used = new Array(s.length).fill(false);
  let content = 0;

  for (let i = 0; i < g.length; i++) {
    let bestJ = -1;
    for (let j = 0; j < s.length; j++) {
      if (!used[j] && s[j] >= g[i] && (bestJ === -1 || s[j] < s[bestJ])) {
        bestJ = j;
      }
    }
    if (bestJ !== -1) {
      used[bestJ] = true;
      content++;
    }
  }
  return content;
}

Line by line:

• used tracks which cookies have already been handed out — a cookie can only go to one child.
• The inner loop scans every cookie for each child and keeps the smallest one that still satisfies s[j] >= g[i]. It must be the smallest sufficient cookie, not just the first one found — handing a child a bigger cookie than necessary can rob a later, pickier child of the only cookie that would have fit them.
• bestJ === -1 after the scan means no cookie was big enough — that child stays unsatisfied, and the loop moves on without incrementing content.
• Nothing here is sorted, and nothing learned while scanning for one child carries over to the next — that repeated O(m) work per child is exactly the O(n·m) cost.

Complexity

Time	Space	Approach
O(n·m)	O(m)	Best-fit linear scan per child, no sorting

Solution 2: Optimal — sort both arrays, two-pointer greedy

Sort g and s ascending. Now the pickiest unsatisfied child is always at the front of g, and the smallest untried cookie is always at the front of s. Walk both with pointers i (child) and j (cookie): if the current cookie is big enough for the current child, it’s the best possible use of that cookie — match them and advance both pointers. If it’s too small, it’s too small for every remaining (equal-or-larger) child too, since they’re sorted ascending — throw it away and advance only the cookie pointer. Neither pointer ever moves backward, so it’s one linear pass after the sort.

g = [2, 3, 5] · s = [1, 3, 4] — sorted ascending, two-pointer scan

Press Play or Step to begin.

Step 0 / 8

▶ Play↺ Reset

The code

function assignCookiesOptimal(g, s) {
  const sortedG = g.slice().sort((a, b) => a - b);
  const sortedS = s.slice().sort((a, b) => a - b);

  let i = 0, j = 0, content = 0;
  while (i < sortedG.length && j < sortedS.length) {
    if (sortedS[j] >= sortedG[i]) {
      content++;
      i++;
      j++;
    } else {
      j++;
    }
  }
  return content;
}

Line by line:

• .slice().sort((a, b) => a - b) — sorts numerically ascending, and copies first so the caller’s original arrays aren’t mutated.
• sortedS[j] >= sortedG[i] is a match: the current cookie satisfies the current (pickiest remaining) child, so it’s used on them — content++, and both pointers advance.
• The else branch only advances j. Since sortedG is ascending, every child after i is at least as picky as g[i] — a cookie too small for g[i] is too small for all of them. It’s permanently wasted, not re-checked later.
• The loop stops the moment either array runs out — there’s nothing left to pair up.

Complexity

Time	Space	Approach
O(n log n + m log m)	O(n + m)	Sort both arrays, then one two-pointer scan

Complexity comparison

Solution	Time	Space
Brute force (best-fit scan per child)	O(n·m)	O(m)
Optimal (sort + two-pointer)	O(n log n + m log m)	O(n + m)

Interview corner

Q: Why does sorting both arrays before the two-pointer scan guarantee the maximum number of content children?

• Once sorted, the child at g[i] is the pickiest child not yet handled, and the cookie at s[j] is the smallest cookie not yet used.
• If that smallest available cookie can satisfy the pickiest remaining child, using any other (larger) cookie on them instead only removes a bigger cookie from the pool without helping — the smaller cookie was already good enough.
• This is an exchange argument: any optimal solution can be rearranged, cookie-swap by cookie-swap, into this smallest-sufficient-cookie-to-pickiest-child pairing without ever reducing the total number of matches — so the greedy choice is never worse than optimal.

Q: Why give each child the SMALLEST sufficient cookie instead of the biggest one available?

• A cookie only needs to clear one bar: s[j] >= g[i]. Any sufficient cookie makes that child equally content — size beyond the requirement is wasted.
• Handing out a large cookie when a small one would do “spends” a resource that a different, pickier child might have specifically needed later.
• Saving the larger cookies preserves the most options for children later in the sorted order — who, by definition, need at least as much.

Q: What happens if there are more children than cookies, or more cookies than children — does the two-pointer solution still work unmodified?

• Yes — the while (i < sortedG.length && j < sortedS.length) condition simply stops as soon as either array is exhausted.
• More children than cookies: the loop ends when j runs out — the leftover, pickiest children at the end of sortedG just never get matched.
• More cookies than children: the loop ends when i runs out — the answer is capped at g.length either way, since each child takes at most one cookie.
• ↳ Common follow-up: “What’s a hard upper bound on the answer, just from the input sizes?” Math.min(g.length, s.length) — you can never content more children than you have cookies, or more children than exist.

Q: Trick question — what does this log?

const g = [10, 2, 1];
console.log(g.sort());

• Answer: [1, 10, 2] — not [1, 2, 10].
• Array .sort() with no comparator converts every element to a string and sorts lexicographically. "10" sorts before "2" because "1" < "2" as characters.
• It also sorts g in place and returns the same array — it doesn’t return a new one.
• ⚠ Trap: this is exactly why both solutions above always pass a numeric comparator — .sort((a, b) => a - b) — to sort g and s. Skip the comparator here and the two-pointer scan silently produces the wrong count on any input with a two-digit value.

Quiz

Quiz: 1. Why does matching the pickiest remaining child with the smallest sufficient cookie never lead to a worse total than some other strategy?

Any optimal pairing can be rearranged into this one, swap by swap, without reducing the number of matches

After sorting, the pickiest remaining child (g[i]) and the smallest remaining usable cookie (s[j]) form a pairing that any optimal solution can be rearranged into without losing matches — so greedily taking it is never worse than optimal.

Quiz: 2. When a cookie is too small for the current child, why can it be discarded permanently instead of just skipped and reconsidered for a later child?

Because children are sorted ascending by greed, every later child needs an equal or larger cookie too

Because children are sorted ascending by greed, every later child needs an equal or larger cookie too.

Quiz: 3. Why does the optimal solution always give a content child the SMALLEST sufficient cookie, never the largest available?

Using a bigger cookie than necessary wastes it — a pickier child later might have needed exactly that size

A cookie only needs to clear the bar s[j] >= g[i]. Handing a child more size than required doesn’t make them any more content, but it does remove a large cookie from the pool that a pickier child later on might specifically need.

Quiz: 4. What causes the two-pointer loop to terminate, and what does that imply about any children left unmatched?

Either pointer running past the end of its array — leftover children (the pickiest ones) simply never get a cookie

The while condition checks both pointers, so the loop stops the instant either array is exhausted. If children run out first, every cookie left over is simply unused; if cookies run out first, every remaining child (the pickiest ones) simply never gets matched.

Quiz: 5. In the optimal solution’s O(n log n + m log m) time complexity, what part of the algorithm is actually responsible for that cost?

Sorting g and s — the two-pointer scan afterward is only O(n + m)

The two-pointer scan itself is O(n + m), a single pass. What actually dominates the runtime is sorting both arrays first, which is O(n log n + m log m) — that’s the real cost of the optimal solution.