Log inSign up
easyLeetCodeNot Started

Assign Cookies

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

You are given two integer arrays: g (greed factor of children) and s (sizes of available cookies). Each child i has a minimum cookie size g[i] required to be content. Each child can receive at most one cookie, and each cookie can be given to at most one child.

Return the maximum number of children you can make content.

Example 1 · Example 1: Basic Matching:

Input: g = [1, 2, 3], s = [1, 1]
Output: 1
Explanation: You have 3 children and 2 cookies. Both cookies have size 1. You can only satisfy the child with greed factor 1. Output is 1.

Example 2 · Example 2: All Satisfied:

Input: g = [1, 2], s = [1, 2, 3]
Output: 2
Explanation: g=[1, 2], s=[1, 2, 3]. Cookie 1 satisfies child 1 (g=1). Cookie 2 satisfies child 2 (g=2). Output is 2.

Constraints:

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why matching minimum demand with minimum sufficient supply is optimal.
  • Implement the two-pointer greedy pattern across 4 languages.
  • Analyze why larger cookies should not be consumed by low-greed children.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two groups where elements in group 1 have requirements met by elements in group 2.
  • Maximize count of satisfied items under one-to-one matching constraint.
  • No penalty for leftover cookies or children.

Algorithmic Decision Tree:

  • Sort both arrays in ascending order.
  • Compare smallest demanding child with smallest available cookie.
  • If s[j] >= g[i], match found -> advance both child and cookie pointers. Else advance cookie pointer.

Connected Patterns:

Assign Mice to HolesBoats to Save PeopleBag of Tokens

1. Brute Force — Quadratic Linear Scan with Visited Array

Intuition

Sort the children array ascending. For each child, loop through all cookies and find the unused cookie of minimum size that is >= child greed. Mark that cookie as used and increment count.

When to apply: When N and M are small (<= 100).

Algorithm

  1. Step 1: Sort children g ascending.
  2. Step 2: Create a boolean array used of size s.length, initialized to false.
  3. Step 3: For each child g[i], find index bestIdx of unused cookie with minimum size >= g[i].
  4. Step 4: If found, mark used[bestIdx] = true and increment count.
  5. Step 5: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findContentChildren(vector<int>& g, vector<int>& s) {
10 sort(g.begin(), g.end());
11 vector<bool> used(s.size(), false);
12 int content = 0;
13
14 for (int greed : g) {
15 int bestIdx = -1;
16 for (int j = 0; j < s.size(); ++j) {
17 if (!used[j] && s[j] >= greed) {
18 if (bestIdx == -1 || s[j] < s[bestIdx]) {
19 bestIdx = j;
20 }
21 }
22 }
23 if (bestIdx != -1) {
24 used[bestIdx] = true;
25 content++;
26 }
27 }
28 return content;
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<int> g = {1, 2, 3};
35 vector<int> s = {1, 1};
36 cout << "Content children: " << sol.findContentChildren(g, s) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N log N + N * M) — Sorting g takes O(N log N). Nested loops run N * M times.
  • Space complexity: O(M) — Boolean used array of size M.

Why Brute Force Doesn't Scale:

With N, M = 30,000, N * M is 9 * 108 operations, which exceeds the 1-second limit. Sorting takes ~30,000 * 15 ~ 4.5 * 105 operations, running in < 10ms.

For N = 30,000 and M = 30,000: O(N log N + M log M) completes in ~8ms compared to ~5 seconds for naive O(N * M).

2. Better — Sort Cookies + Binary Search with Removal

Intuition

Store cookie sizes in a multiset or sorted structure. For each child greed factor, search for the lower bound (first cookie >= g[i]). If found, remove it and increment count.

When to apply: When using multiset / TreeSet data structures.

Algorithm

  1. Step 1: Sort greed factors g ascending.
  2. Step 2: Insert all cookies into a multiset (in C++) or sort cookies.
  3. Step 3: For each child greed, query lower_bound(greed).
  4. Step 4: If an iterator exists, erase that cookie and increment count.
  5. Step 5: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <set>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int findContentChildren(vector<int>& g, vector<int>& s) {
11 sort(g.begin(), g.end());
12 multiset<int> cookies(s.begin(), s.end());
13 int content = 0;
14
15 for (int greed : g) {
16 auto it = cookies.lower_bound(greed);
17 if (it != cookies.end()) {
18 content++;
19 cookies.erase(it);
20 }
21 }
22 return content;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> g = {1, 2, 3};
29 vector<int> s = {1, 1};
30 cout << "Content children: " << sol.findContentChildren(g, s) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N + M log M + N log M) — Building BST / multiset takes O(M log M). N queries take O(N log M).
  • Space complexity: O(M) — BST stores M cookies.

3. Optimal — Sort Both Arrays + Two Pointers

Intuition

Sort greed factors g and cookie sizes s ascending. With pointer i for children and j for cookies: if s[j] >= g[i], the cookie meets child i's demand, so increment i (child satisfied). Regardless, increment j (cookie is consumed or too small). When either pointer reaches the end, i is the maximum number of satisfied children.

When to apply: Always for Assign Cookies.

Algorithm

  1. Step 1: Sort children greed array g in ascending order.
  2. Step 2: Sort cookie sizes array s in ascending order.
  3. Step 3: Initialize child pointer i = 0 and cookie pointer j = 0.
  4. Step 4: While i < g.length and j < s.length: if s[j] >= g[i], advance i; always advance j.
  5. Step 5: Return i (total content children).

Interactive Trace for Assign Cookies

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compare child 0 (greed 1) with cookie 0 (size 1)
Visual state
Values and pointers at this exact step
pointers
S
satisfied
pending
used
available
available
0
↑ child_ptr
1
2
↑ cookie_ptr
3
4
Check / comparison
1 >= 1 (Cookie satisfies child)
Decision / next transition
Assign cookie 0 to child 0. Advance both pointers: child i=1, cookie j=1.
Why this step matters

Step 1: Compare child 0 (greed 1) with cookie 0 (size 1). s[0] >= g[0].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findContentChildren(vector<int>& g, vector<int>& s) {
10 sort(g.begin(), g.end());
11 sort(s.begin(), s.end());
12
13 int child = 0;
14 int cookie = 0;
15
16 while (child < g.size() && cookie < s.size()) {
17 if (s[cookie] >= g[child]) {
18 child++;
19 }
20 cookie++;
21 }
22 return child;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> g = {1, 2, 3};
29 vector<int> s = {1, 1};
30 cout << "Content children: " << sol.findContentChildren(g, s) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N + M log M) — Sorting g takes O(N log N) and sorting s takes O(M log M). Two-pointer pass is linear O(N + M).
  • Space complexity: O(1) auxiliary — Uses only two integer pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Quadratic Linear Scan with Used ArrayO(N * M)O(M) used trackerFor each child, scan through the cookies to find the smallest unused cookie with size >= g[i].Linear scan per child.
2.Better — Sort Cookies + Binary SearchO(M log M + N log M)O(M) boolean used arraySort cookies. For each child, binary search the first cookie >= g[i], linear search next available unused cookie.Maintaining dynamic availability of cookies.
3.Optimal — Sort Both + Two PointersOptimalO(N log N + M log M)O(1) auxiliarySort both g and s ascending. Use pointer i for children and j for cookies. If s[j] >= g[i], child i is satisfied (i++). Always advance cookie pointer j++.Sorting step.

Common Pitfalls & Crucial Edge Cases

Sorting in descending order without updating pointer logic

Ascending sort is simpler and guarantees using the smallest valid cookie first.

Advancing child pointer when cookie is too small

Child is NOT satisfied if s[cookie] < g[child]; only the cookie pointer should advance.

Crucial Edge Cases to Validate:

  • No cookies available (s is empty) — Returns 0 immediately.
  • All cookies smaller than all greed factors — No child can be satisfied; returns 0.
  • Every cookie is larger than any greed factor — Minimum of children count and cookies count is returned.
  • Duplicate greed factors or cookie sizes — Handled naturally by two pointers.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the greedy choice clearly: 'I want to minimize cookie waste by matching the smallest feasible cookie to each child in increasing order of greed.'
  2. Mention that this problem is a classic introduction to the two-pointer greedy pattern.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we pair the least demanding child with the smallest sufficient cookie?

Back to DSA Sheet