Assign Cookies (Greedy Matching of Smallest Sufficient Resource)

• Assign Cookies – a greedy matching problem that maximises the number of satisfied children by pairing each with the smallest sufficient cookie.
• Sort-and-sweep – sort greed factors and cookie sizes ascending, then sweep with two pointers to match greedily.
• Smallest sufficient rule – for the least greedy unsatisfied child, advance cookies until one is large enough, never wasting a large cookie on a child a smaller one could serve.
• Exchange argument – giving the smallest sufficient resource to the least demanding claimant can never reduce the total count of satisfied claimants.
• Complexity – O(n log n) for sorting, O(n) for the sweep, and O(1) extra space beyond the sort.

What is the Assign Cookies problem?

Assign Cookies gives you two arrays: greed factors for children and sizes for cookies. A child is content only if they receive a cookie whose size is at least as large as their greed factor. Each cookie can be assigned to at most one child. The goal is to maximise the number of content children.

package com.bank.service;

import java.util.Arrays;

public class AssignCookies {
    public int findContentChildren(int[] greed, int[] size) {
        Arrays.sort(greed);
        Arrays.sort(size);
        int child = 0, cookie = 0;
        while (child < greed.length && cookie < size.length) {
            if (size[cookie] >= greed[child]) {
                child++;  // this child is satisfied
            }
            cookie++;     // move to next cookie either way
        }
        return child;
    }
}

Why does sorting and sweeping work?

Sorting both arrays puts the least demanding child and the smallest cookie at the front. By trying to satisfy the least demanding child first with the smallest available cookie, we never waste a large resource where a small one would do. If a cookie is too small for even the least demanding unsatisfied child, it is useless for all remaining children and can be discarded.

package com.bank.service;

public class SortSweepDemo {
    public static void main(String[] args) {
        // Greed: [1, 2, 3], Sizes: [1, 1]
        // After sort: greed=[1,2,3], size=[1,1]
        // cookie=0 (size=1) >= greed[0] (1): child satisfied, child=1
        // cookie=1 (size=1) < greed[1] (2): skip cookie
        // No more cookies. Answer: 1
        int[] greed = {1, 2, 3};
        int[] size = {1, 1};
        AssignCookies ac = new AssignCookies();
        System.out.println("Content children: " + ac.findContentChildren(greed, size));
    }
}

Content children: 1

How does the exchange argument prove correctness?

The exchange argument states: if any optimal solution used a larger cookie for a child that a smaller cookie could have satisfied, we can swap in the smaller cookie without reducing the total count. The freed larger cookie can then satisfy a needier child or remain unused. This means the greedy matching is at least as good as any other assignment.

// Exchange argument example:
// Child A needs 2, Child B needs 5
// Cookies available: [3, 6]
//
// Optimal: give 3 to A, 6 to B -> 2 satisfied
// Greedy: give 3 to A (smallest sufficient), 6 to B -> 2 satisfied (same)
//
// Wrong: give 6 to A, 3 to B (3 < 5, B unsatisfied) -> 1 satisfied
// The greedy never wastes the large cookie on the small need.

What is the time and space complexity?

The dominant cost is sorting both arrays. The two-pointer sweep after sorting runs in linear time because each pointer moves forward at most once per step.

• Time complexity – O(g log g + s log s) where g is the number of children and s is the number of cookies.
• Space complexity – O(1) extra beyond the sort (or O(g + s) if the sort allocates temporary space).
• Sweep cost – O(g + s) for the two-pointer pass.

// Sorting: O(g log g) + O(s log s)
Arrays.sort(greed);
Arrays.sort(size);

// Sweep: O(g + s)
while (child < greed.length && cookie < size.length) {
    // each pointer advances at most once per iteration
}

What are the edge cases?

Edge cases include empty arrays, a case where no cookie satisfies any child, and a case where every child can be satisfied.

package com.bank.service;

public class CookieEdgeCases {
    public static void main(String[] args) {
        AssignCookies ac = new AssignCookies();

        // No children
        System.out.println(ac.findContentChildren(new int[]{}, new int[]{1,2}));  // 0

        // No cookies
        System.out.println(ac.findContentChildren(new int[]{1,2}, new int[]{}));  // 0

        // No cookie big enough
        System.out.println(ac.findContentChildren(new int[]{5,6}, new int[]{1,2})); // 0

        // All children satisfied
        System.out.println(ac.findContentChildren(new int[]{1,2}, new int[]{3,4})); // 2
    }
}

0
0
0
2

What are common mistakes?

The most common mistake is not sorting both arrays before sweeping. Without sorting, the two-pointer approach does not guarantee optimal matching. Another mistake is advancing the child pointer even when the current cookie is too small.

// WRONG: advancing child when cookie is too small
while (child < greed.length && cookie < size.length) {
    if (size[cookie] >= greed[child]) {
        child++;
    } else {
        child++;  // WRONG: skipping unsatisfied child
    }
    cookie++;
}

// CORRECT: only advance child when satisfied
while (child < greed.length && cookie < size.length) {
    if (size[cookie] >= greed[child]) {
        child++;  // child satisfied, move to next child
    }
    cookie++;     // always move to next cookie
}

How is this different from the Assignment Problem?

Assign Cookies is a simplified one-dimensional matching problem. The general Assignment Problem assigns agents to tasks with varying costs, requiring the Hungarian algorithm with O(n cubed) complexity. Here, both demands and resources are one-dimensional, so sorting reduces the problem to a linear sweep.

| Aspect | Assign Cookies | General Assignment Problem |
|---|---|---|
| Dimensions | Single (greed vs size) | Multi-dimensional cost matrix |
| Strategy | Sort + two pointers | Hungarian algorithm |
| Complexity | O(n log n) | O(n cubed) |
| Constraint | Each cookie to at most one child | Each agent to exactly one task |

// Assign Cookies: 1D greedy
Arrays.sort(greed);
Arrays.sort(size);
// sweep with two pointers

// General Assignment: needs cost matrix
// int[][] cost = new int[n][n];
// hungarianAlgorithm(cost); // O(n^3)

How would you apply this in a banking system?

At the National Bank of India, a limited pool of credit facilities of varying sizes must be allocated to loan applicants who each need at least a minimum credit amount. The system maximises the number of applicants served by sorting both sides and matching each applicant to the smallest facility that meets their minimum.

package com.bank.service;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.List;

public class CreditFacilityAllocator {
    public int allocateFacilities(
            BigDecimal[] applicantMinimums, BigDecimal[] facilityAmounts) {
        Arrays.sort(applicantMinimums);
        Arrays.sort(facilityAmounts);
        int served = 0, facility = 0;
        while (served < applicantMinimums.length
                && facility < facilityAmounts.length) {
            if (facilityAmounts[facility].compareTo(
                    applicantMinimums[served]) >= 0) {
                served++;
            }
            facility++;
        }
        return served;
    }
}

What should a senior engineer know?

A senior engineer should recognise this as a general pattern: whenever demand and supply are both one-dimensional and the goal is to maximise matches, sort both sides and sweep with two pointers. The exchange argument proves correctness in all such cases. They should also know that if ties exist, the greedy still works because any sufficient cookie is equally valid among ties.

// The pattern generalises to any 1D matching:
// 1. Sort demands ascending
// 2. Sort supplies ascending
// 3. Two-pointer sweep: match smallest sufficient supply to least demanding
// 4. Exchange argument: swapping a larger supply for a smaller sufficient one
//    never reduces the match count.