easy

Assign Cookies

Hand out cookies to as many children as possible while satisfying their minimum size needs.

1. Define the problem

Assign Cookies

Each child i has a greed factor gi — the smallest cookie size that will satisfy them. Each cookie j has a size sj, and a cookie can satisfy at most one child if sj is greater than or equal to gi. Return the maximum number of content children you can satisfy. Sort both arrays, then use a greedy two-pointer sweep: give the least fussy remaining child the smallest cookie that still satisfies them, so bigger cookies stay available for fussier children.

Constraints

  • 1 ≤ g.length ≤ 3 × 104
  • 0 ≤ s.length ≤ 3 × 104
  • 1 ≤ gi, sj ≤ 231 - 1

Example

Inputg = [1, 2, 3], s = [1, 1]
Output1

Explanation You only have two cookies of size 1. Even though you have 3 children, only one (greed factor 1) can be satisfied.

2. Know the words first

In plain terms

Greed factor
The minimum cookie size a child will accept — a greed factor of 3 means only a cookie of size 3 or bigger will content them.
3. Visualize the solution

Sweep sorted cookies against sorted greed factors

Sweep sorted cookies against sorted greed factors
Statusi=0, j=0

greed[0]=1, cookies[0]=1 — the cookie is big enough for this child.

What happens in this step

sorted greed = [1, 2, 3], sorted cookies = [1, 1]
i=0 -> greed[0]=1, j=0 -> cookies[0]=1

cookies[j] >= greed[i] since 1 >= 1, so the smallest remaining cookie can satisfy the least fussy remaining child — this is the locally-best pairing to make right now.
Step 1 of 4

Steps to visualize

  1. Sort the greed factors and the cookie sizes.
  2. Compare the smallest unassigned cookie to the least fussy unsatisfied child.
  3. If the cookie is big enough, hand it over and advance both pointers.
  4. If the cookie is too small, it cannot satisfy anyone left, so skip it and advance only the cookie pointer.
  5. Repeat until either every child is satisfied or every cookie is used.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sweep sorted cookies against sorted greed factors
Statusi=0, j=0

greed[0]=1, cookies[0]=1 — the cookie is big enough for this child.

What happens in this step

sorted greed = [1, 2, 3], sorted cookies = [1, 1]
i=0 -> greed[0]=1, j=0 -> cookies[0]=1

cookies[j] >= greed[i] since 1 >= 1, so the smallest remaining cookie can satisfy the least fussy remaining child — this is the locally-best pairing to make right now.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findContentChildren(g, s) {
  const greed = [...g].sort((a, b) => a - b);
  const cookies = [...s].sort((a, b) => a - b);
  let i = 0;
  let j = 0;
  let count = 0;

  while (i < greed.length && j < cookies.length) {
    if (cookies[j] >= greed[i]) {
      count++;
      i++;
      j++;
    } else {
      j++;
    }
  }

  return count;
}
Time
O(n log n + m log m)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
g = [1, 2, 3], s = [1, 1]1example from the docstring
g = [1, 2], s = [1, 2, 3]2enough cookies of every size, both children satisfied
g = [1, 2], s = []0no cookies available at all
g = [2], s = [1, 2, 3]1more cookies than children, only one child to satisfy
g = [5, 5, 5], s = [1, 1, 1]0every cookie is too small for every child
g = [1, 2, 3], s = [1, 2, 3]3every cookie exactly matches a greed factor
g = [], s = [1, 2, 3]0no children to satisfy

Keep reading