Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Assign Cookies

EASYProblemSolveExternal Links

Description

Assume you are an awesome parent and want to give your children some cookies. But you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with. Each cookie j has a size s[j]. If s[j] >= g[i], we can assign cookie j to child i, and child i will be content.

Your goal is to maximize the number of content children and output the maximum number.

Key Rules:

  • Each child can receive at most one cookie.
  • Each cookie can be assigned to at most one child.
  • A child is content only if the cookie size meets or exceeds their greed factor.

Examples

Example 1

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

Output: 1

Explanation: You have 3 children with greed factors 1, 2, and 3, and only 2 cookies, both of size 1. Only the child with greed factor 1 can be satisfied (1 ≥ 1). The children with greed factors 2 and 3 cannot be satisfied with cookies of size 1. So the maximum number of content children is 1.

Example 2

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

Output: 2

Explanation: You have 2 children with greed factors 1 and 2, and 3 cookies of sizes 1, 2, and 3. Assign cookie of size 1 to child with greed 1, and cookie of size 2 to child with greed 2. Both children are satisfied. (The cookie of size 3 is unused.) Maximum content children = 2.

Example 3

Input: g = [1,3,5,7], s = [2,3,4,6]

Output: 3

Explanation: Sort both: children greed = [1,3,5,7], cookies = [2,3,4,6].

  • Child greed 1: cookie size 2 works (2 ≥ 1). Assign.
  • Child greed 3: cookie size 3 works (3 ≥ 3). Assign.
  • Child greed 5: cookie size 4 is too small (4 < 5). Skip. Cookie size 6 works (6 ≥ 5). Assign.
  • Child greed 7: no cookies left. Cannot satisfy.

Maximum content children = 3.

Constraints

  • 1 ≤ g.length ≤ 3 × 10⁴
  • 0 ≤ s.length ≤ 3 × 10⁴
  • 1 ≤ g[i], s[j] ≤ 2³¹ - 1

Editorial

Brute Force

Intuition

The most straightforward approach is: for each child, scan through all available cookies to find one that satisfies them.

Imagine you're handing out cookies at a school. You call each child up one by one and rummage through your basket to find a suitable cookie. For each child, you look through every remaining cookie to find the smallest one that meets their demand — you don't want to waste a large cookie on a child who'd be happy with a smaller one.

To ensure correctness, we sort both arrays first. This way, we process children from the least greedy to the most greedy, and the first suitable unused cookie we find is also the smallest one available. This avoids "wasting" large cookies on less greedy children.

For each child (outer loop), we scan all cookies (inner loop), skipping any that are already used or too small. When we find a match, we mark the cookie as used and move to the next child.

Step-by-Step Explanation

Let's trace with g = [1, 3, 5, 7] and s = [2, 3, 4, 6] (both already sorted):

Step 1: Child 0 (greed = 1). Scan cookies:

  • Cookie 0 (size 2): 2 ≥ 1? Yes! Assign cookie 0. Mark used. count = 1.

Step 2: Child 1 (greed = 3). Scan cookies:

  • Cookie 0 (size 2): Used, skip.
  • Cookie 1 (size 3): 3 ≥ 3? Yes! Assign cookie 1. Mark used. count = 2.

Step 3: Child 2 (greed = 5). Scan cookies:

  • Cookie 0: Used, skip.
  • Cookie 1: Used, skip.
  • Cookie 2 (size 4): 4 ≥ 5? No, too small.
  • Cookie 3 (size 6): 6 ≥ 5? Yes! Assign cookie 3. Mark used. count = 3.

Step 4: Child 3 (greed = 7). Scan cookies:

  • Cookies 0, 1, 3 are used. Cookie 2 (size 4): 4 < 7. No suitable cookie found.

Result: 3 children satisfied.

Brute Force — Scanning All Cookies for Each Child — Watch how the brute force scans through the cookies array for every child, skipping used cookies. Notice the repeated scanning — this is the source of the O(n × m) inefficiency.

Algorithm

  1. Sort both arrays g (greed factors) and s (cookie sizes) in ascending order.
  2. Create a boolean array used of size m (number of cookies), initialized to false.
  3. Initialize count = 0.
  4. For each child (iterate through sorted g):
    a. Scan all cookies from index 0 to m-1.
    b. If cookie j is not used AND s[j] >= g[i], assign it: mark used[j] = true, increment count, and break.
  5. Return count.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findContentChildren(
        vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        vector<bool> used(s.size(), false);
        int count = 0;

        for (int i = 0; i < g.size(); i++) {
            for (int j = 0; j < s.size(); j++) {
                if (!used[j]
                    && s[j] >= g[i]) {
                    used[j] = true;
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};
class Solution:
    def findContentChildren(
        self, g: list[int], s: list[int]
    ) -> int:
        g.sort()
        s.sort()
        used = [False] * len(s)
        count = 0

        for greed in g:
            for j in range(len(s)):
                if not used[j] \
                   and s[j] >= greed:
                    used[j] = True
                    count += 1
                    break

        return count
import java.util.Arrays;

class Solution {
    public int findContentChildren(
        int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        boolean[] used = new boolean[s.length];
        int count = 0;

        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < s.length; j++) {
                if (!used[j]
                    && s[j] >= g[i]) {
                    used[j] = true;
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n × m + n log n + m log m)

Sorting takes O(n log n + m log m) where n = |g| and m = |s|. The nested loop takes O(n × m) in the worst case: for each of the n children, we may scan all m cookies. The dominant term is O(n × m).

For n = m = 30,000, this is 9 × 10⁸ operations — likely too slow for competitive programming time limits.

Space Complexity: O(m)

The used boolean array requires O(m) extra space to track which cookies have been assigned.

Why This Approach Is Not Efficient

The brute force's O(n × m) nested scanning is wasteful because it re-scans cookies that we've already determined are too small or used.

Consider what happens with sorted arrays: when processing child i (greed = 5), we skip used cookies 0 and 1, then discover cookie 2 (size 4) is too small. When processing child i+1 (greed = 7), we skip the SAME used cookies 0, 1 and the SAME too-small cookie 2 all over again. This redundant scanning is the bottleneck.

Key Insight: Since both arrays are sorted, once a cookie is too small for a child, it's also too small for every subsequent (greedier) child. And once a cookie is used, it stays used. So we never need to go backwards — we can maintain a single pointer into the cookies array that only moves forward.

This is the classic two-pointer technique: process both sorted arrays in a single pass, with each pointer advancing monotonically. This eliminates all redundant scanning and reduces the matching phase from O(n × m) to O(n + m).

Optimal Approach - Sort + Two Pointers (Greedy)

Intuition

The optimal approach uses a greedy strategy with two pointers: always try to satisfy the least greedy child with the smallest cookie that works.

Think of it like distributing exam scores. If you have rewards of different values and students who need minimum scores to be happy, the smartest strategy is:

  1. Sort students by their minimum requirement (least demanding first).
  2. Sort rewards by value (smallest first).
  3. For each student starting from the least demanding, give them the smallest available reward that meets their need.

Why is this greedy strategy optimal? Because satisfying a less demanding child with a small cookie never hurts — it leaves larger cookies available for greedier children. If we gave a large cookie to a less demanding child, we'd potentially waste it when a smaller cookie would have sufficed.

Implementation with two pointers:

  • Pointer i walks through children (sorted by greed, ascending).
  • Pointer j walks through cookies (sorted by size, ascending).
  • If the current cookie satisfies the current child (s[j] >= g[i]): assign it, advance both pointers.
  • If the current cookie is too small: skip it (advance only j), since this cookie can't help any remaining child either.
  • Stop when either pointer reaches the end.

Both pointers only move forward — the entire matching runs in O(n + m).

Step-by-Step Explanation

Let's trace with g = [1, 3, 5, 7] and s = [2, 3, 4, 6] (both sorted):

Step 1: i = 0, j = 0. Child greed = 1, cookie size = 2.

  • 2 ≥ 1? Yes. Assign cookie 0 to child 0. count = 1. Advance both: i = 1, j = 1.

Step 2: i = 1, j = 1. Child greed = 3, cookie size = 3.

  • 3 ≥ 3? Yes. Perfect match. Assign. count = 2. Advance both: i = 2, j = 2.

Step 3: i = 2, j = 2. Child greed = 5, cookie size = 4.

  • 4 ≥ 5? No. Cookie too small. Advance only j. j = 3.
  • Key: this cookie (size 4) can't satisfy child 2 (greed 5) or child 3 (greed 7). It's forever useless, so we skip it.

Step 4: i = 2, j = 3. Child greed = 5, cookie size = 6.

  • 6 ≥ 5? Yes. Assign. count = 3. Advance both: i = 3, j = 4.

Step 5: j = 4 is out of bounds (only 4 cookies). We've exhausted all cookies. Stop.

Result: 3 children satisfied. We made exactly 5 comparisons total — one per pointer advance. No wasted work.

Optimal Greedy — Two Pointers Never Go Back — Watch how the cookie pointer j only moves forward. When a cookie is too small, we skip it permanently since all remaining children are greedier. This single-pass approach eliminates the brute force's redundant scanning.

Algorithm

  1. Sort both arrays g (greed factors) and s (cookie sizes) in ascending order.
  2. Initialize two pointers: i = 0 (children), j = 0 (cookies), and count = 0.
  3. While i < n AND j < m:
    a. If s[j] >= g[i]: cookie satisfies the child. Increment count and i (move to next child).
    b. Always increment j (move to next cookie — whether it was assigned or skipped).
  4. Return count.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findContentChildren(
        vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0, count = 0;

        while (i < g.size()
               && j < s.size()) {
            if (s[j] >= g[i]) {
                count++;
                i++;
            }
            j++;
        }
        return count;
    }
};
class Solution:
    def findContentChildren(
        self, g: list[int], s: list[int]
    ) -> int:
        g.sort()
        s.sort()
        i = j = count = 0

        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                count += 1
                i += 1
            j += 1

        return count
import java.util.Arrays;

class Solution {
    public int findContentChildren(
        int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0, count = 0;

        while (i < g.length
               && j < s.length) {
            if (s[j] >= g[i]) {
                count++;
                i++;
            }
            j++;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n log n + m log m)

Sorting the children array takes O(n log n) and sorting the cookies array takes O(m log m). The two-pointer matching loop runs in O(n + m) since each pointer advances at most n or m times respectively. The sorting dominates, giving O(n log n + m log m) total.

For n = m = 30,000, this is about 30,000 × 15 ≈ 450,000 operations — over 1000× faster than the brute force's 9 × 10⁸.

Space Complexity: O(1) auxiliary

Beyond the input arrays, we only use three integer variables (i, j, count). The sorting is done in-place. If counting the sorting stack space, it's O(log n + log m).

Compared to the brute force which needed O(m) extra space for the used array, this approach is also more space-efficient.