☕ DSA Java Articles

Topics › Greedy Algorithms › Easy Problems

Assign Cookies

Easy TUF ID 2834 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You have some children and some cookies. Child i has a greed factor greed[i]: the smallest cookie size that will make that child content. Cookie j has size cookies[j]. Each child can receive at most one cookie and each cookie can go to at most one child. A child is content when the cookie they receive has size >= greed[i]. Return the maximum number of content children.

Constraints: 0 ≤ n, m ≤ 3 × 10^4 (children and cookies), and every greed factor and cookie size is between 1 and 2^31 - 1. The algorithms only compare values, never add them, so overflow is not a concern.

Example 1

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

Example 2

greed = [1, 2], cookies = [1, 2, 3]
answer = 2          // give size 1 to greed 1 and size 2 (or 3) to greed 2

The greedy insight

Before writing any code it helps to see why a simple rule is safe: satisfy the least greedy child first, using the smallest cookie that is big enough.

Once c and x are matched, the rest is the same problem on fewer children and cookies, so applying the rule repeatedly is optimal. The two approaches below both follow this rule; they differ only in how fast they find “the smallest cookie that fits”.

Approach 1: Brute force, linear search for every child

Intuition. Sort the children by greed so we serve them easiest first. For each child, look through all cookies and pick the smallest unused one that is large enough. If no cookie fits this child, no cookie fits any later child either, because later children are greedier, so we can stop.

Algorithm.

  1. Copy and sort greed in ascending order. Keep a used flag per cookie.
  2. For each greed value need in that order:
    • Scan every cookie and remember the index of the smallest unused cookie with size >= need.
    • If none exists, stop. Otherwise mark it used and count one more content child.
  3. Return the count.
static int bruteForce(int[] greed, int[] cookies) {
    int[] g = greed.clone();
    Arrays.sort(g);
    boolean[] used = new boolean[cookies.length];
    int content = 0;
    for (int need : g) {
        int pick = -1;
        for (int j = 0; j < cookies.length; j++) {
            if (!used[j] && cookies[j] >= need && (pick == -1 || cookies[j] < cookies[pick])) pick = j;
        }
        if (pick == -1) break;            // nothing fits this child, so nothing fits a greedier one
        used[pick] = true;
        content++;
    }
    return content;
}

Complexity. Time O(n log n + n·m): sorting the children, then a full scan of the m cookies for each of the n children. Space O(n + m) for the sorted copy and the used flags.

With 3 × 10^4 children and cookies this is about 9 × 10^8 comparisons. It works, but it repeats the same search over and over. The waste is obvious: once cookies are sorted, the “smallest unused cookie that fits” only ever moves forward.

Approach 2: Optimal, sort both and use two pointers

Intuition. Sort both arrays. Keep a pointer child at the least greedy child still waiting and a pointer cookie at the smallest cookie not yet considered. Look at the current cookie:

Either way the cookie is finished with, so cookie always advances. Because children are served in increasing greed and cookies are tried in increasing size, the first cookie that fits a child is exactly the smallest sufficient one from the exchange argument above.

Algorithm.

  1. Copy and sort both arrays. Set child = 0, cookie = 0.
  2. While both pointers are in range:
    • If s[cookie] >= g[child], do child++.
    • Do cookie++.
  3. Return child, which equals the number of satisfied children.
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++;   // smallest remaining cookie satisfies the least greedy waiting child
        cookie++;                             // the cookie is either given away or too small for everyone left
    }
    return child;
}

Dry run on greed = [10, 9, 8, 7], cookies = [5, 6, 7, 8]. After sorting, g = [7, 8, 9, 10] and s = [5, 6, 7, 8].

cookie s[cookie] child g[child] fits? action
0 5 0 7 no discard cookie
1 6 0 7 no discard cookie
2 7 0 7 yes child becomes 1
3 8 1 8 yes child becomes 2

Cookies run out, so the answer is 2: the children with greed 7 and 8 are content.

Complexity. Time O(n log n + m log m) for the two sorts; the sweep itself is O(n + m) because each step advances cookie. Space O(n + m) for the copies. If you are allowed to sort the input arrays in place, the extra space drops to the sort’s own stack.

The method sorts copies so the caller’s arrays keep their order. In an interview you can sort in place, but saying so explicitly shows you noticed the side effect.

Edge cases and pitfalls