☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Assign Cookies

Easy TUF ID 541 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

There are n children and m cookies. Child i has a greed factor greed[i], the minimum cookie size that will make them content. Cookie j has size cookies[j]. Each child may receive at most one cookie and each cookie may go to at most one child. A child who receives a cookie of size ≥ greed[i] is content. Return the largest number of children that can be made content.

This is LeetCode 455. Constraints: 0 ≤ n, m ≤ 3 × 10^4 (LeetCode guarantees at least one child) and 1 ≤ greed[i], cookies[j] ≤ 2^31 - 1. The algorithms only compare values and never add them, so the large values cause no overflow.

Although the A2Z list places this row next to the DP-on-subsequences problems, it is a greedy problem (the SDE sheet files it under Greedy). The first approach below shows what a “try every choice” search looks like here; the other two show why that search is unnecessary.

Example 1

greed = [1, 2, 3], cookies = [1, 1]
answer = 1          // both cookies have size 1, so only the child with greed 1 can be helped

Example 2

greed = [10, 9, 8, 7], cookies = [5, 6, 7, 8]
answer = 2          // cookie 7 to the child with greed 7, cookie 8 to the child with greed 8

Approach 1: Brute force, try every assignment

Intuition. Without any insight, we can let each child in turn either go without, or take any unused cookie that is big enough, and keep the best total over all these choices. That is a pick / not-pick search, like the subsequence recursions, except that “pick” can choose among several cookies. It is guaranteed correct because it literally examines every legal assignment, which makes it a useful reference for checking the faster methods.

Algorithm.

  1. tryAll(i): if every child has been considered, return 0.
  2. Start with best = tryAll(i + 1), the option where child i gets nothing.
  3. For each unused cookie j with cookies[j] ≥ greed[i]: mark it used, update best = max(best, 1 + tryAll(i + 1)), unmark it.
  4. Return best.
static int bruteForce(int[] greed, int[] cookies) {
    return tryAll(0, greed, cookies, new boolean[cookies.length]);
}

static int tryAll(int i, int[] greed, int[] cookies, boolean[] used) {
    if (i == greed.length) return 0;
    int best = tryAll(i + 1, greed, cookies, used);              // child i gets nothing
    for (int j = 0; j < cookies.length; j++) {
        if (!used[j] && cookies[j] >= greed[i]) {                  // child i gets cookie j
            used[j] = true;
            best = Math.max(best, 1 + tryAll(i + 1, greed, cookies, used));
            used[j] = false;
        }
    }
    return best;
}

Complexity. Time is exponential, up to about (m + 1)^n branches, since every child has up to m + 1 options. Space O(n + m) for the recursion and the used flags. Memoization does not rescue it: the set of used cookies is part of the state, and there are 2^m such sets.

Why greedy is safe

Two observations remove the search entirely.

  1. Serve the least greedy children. If some group of k children can all be made content, then the k least greedy children can be too: hand each of them a cookie taken from a greedier child in the group. Their needs are smaller, so the cookies still suffice. Nothing is lost by focusing on the easiest children.
  2. Give the smallest cookie that is big enough. Suppose an optimal assignment gives the least greedy child c a cookie larger than x, the smallest cookie that fits c. Exchange: give x to c and give c’s old, larger cookie to whoever held x (if anyone did). That person is still content, since their new cookie is bigger. The count is unchanged, so there is an optimal answer in which c gets exactly x.

After matching c with x, what remains is the same problem with one fewer child and cookie, so applying the rule repeatedly builds an optimal assignment. A useful corollary: if the smallest-greed child left cannot be satisfied by any remaining cookie, no greedier child can be either, so we may stop.

Intuition. Apply the greedy rule literally. Sort the children by greed. Keep the unused cookies in a TreeMap from size to count, which acts as a sorted multiset. For each child, ceilingKey(need) returns the smallest available size ≥ need in O(log m) time. Take one cookie of that size, removing the key when its count drops to zero.

Algorithm.

  1. Put every cookie into the TreeMap (size to count). Copy and sort greed.
  2. For each need in ascending order: find size = ceilingKey(need). If it is null, stop. Otherwise decrement that size’s count and count one content child.
  3. Return the count.
static int better(int[] greed, int[] cookies) {
    TreeMap<Integer, Integer> left = new TreeMap<>();              // cookie size -> how many are unused
    for (int c : cookies) left.merge(c, 1, Integer::sum);
    int[] g = greed.clone();
    Arrays.sort(g);
    int content = 0;
    for (int need : g) {
        Integer size = left.ceilingKey(need);                      // smallest unused cookie with size >= need
        if (size == null) break;                                   // nothing fits; greedier children fare no better
        if (left.merge(size, -1, Integer::sum) == 0) left.remove(size);
        content++;
    }
    return content;
}

Complexity. Time O(n log n + m log m): sorting the children, building the map, and one O(log m) lookup and update per child. Space O(n + m) for the sorted copy and the map.

This version is worth knowing because it generalises: if children arrived one at a time and had to be served immediately, the multiset still finds the best cookie for each one. Here, though, everything is known in advance, so we can do the matching with plain arrays.

Approach 3: Optimal, two pointers on two sorted arrays

Intuition. Sort the cookies as well. Walk through the cookies in increasing size while a pointer child marks the least greedy child not yet served. If the current cookie satisfies that child, it is the smallest cookie that does (all smaller ones have already been passed over), so the greedy rule assigns it: move both pointers. If it does not, the cookie is too small for this child and therefore for every greedier child after it, so it is useless and we discard it. Either way the cookie pointer advances.

The final value of child is the number of content children.

Algorithm.

  1. Copy and sort both arrays.
  2. While both pointers are in range: if s[cookie] ≥ g[child], do child++. Always do cookie++.
  3. Return child.
static int optimal(int[] greed, int[] cookies) {
    int[] g = greed.clone(), s = cookies.clone();
    Arrays.sort(g);
    Arrays.sort(s);
    int child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) child++;                        // this cookie satisfies the least greedy child left
        cookie++;                                                  // used or too small for everyone left: discard it
    }
    return child;
}

Dry run on Example 2 (g = [7, 8, 9, 10], s = [5, 6, 7, 8] after sorting):

cookie size child (greed) fits? content so far
0 5 0 (7) no, discard 0
1 6 0 (7) no, discard 0
2 7 0 (7) yes 1
3 8 1 (8) yes 2

The cookies run out, so the answer is 2.

Complexity. Time O(n log n + m log m) for the sorts; the sweep is O(n + m). Space O(n + m) for the sorted copies (O(1) extra if sorting the inputs in place is allowed). Asymptotically this ties with Approach 2, but it uses no tree, has a far smaller constant, and becomes linear when the inputs are already sorted.

Edge cases and pitfalls