Assign Cookies

LeetCode 455: Assign Cookies Solution & Explanation

Problem Overview

TL;DR: To maximize the number of content children, sort both the greed factors and cookie sizes, then iterate through them to assign the smallest sufficient cookie to the child with the smallest greed factor.

In the Assign Cookies problem, we are provided with two arrays: g representing the greed factor of each child (the minimum cookie size they will accept) and s representing the sizes of available cookies. Each child can receive at most one cookie. A child i is content only if they receive a cookie j where s[j] >= g[i]. Our objective in LeetCode 455 is to determine the maximum number of children we can satisfy given the available inventory.

Brute Force Approach for Assign Cookies

A naive or brute force approach might attempt to find the optimal assignment by checking every possible combination of children and cookies. Without a structured order, one might iterate through each child and attempt to find the "best" cookie for them from the remaining pile, or generate all permutations of assignments to see which yields the highest count.

Pseudo-code for a Naive Approach:

Initialize max_content_children = 0
For every permutation of children:
    For every permutation of cookies:
        Count how many valid assignments (s[j] >= g[i]) occur strictly in order
        Update max_content_children if current count is higher
Return max_content_children

Time Complexity: The complexity of generating permutations is factorial, effectively $O(N!)$ or $O(M!)$. Even a slightly optimized nested loop approach that tries to match every child to every cookie without sorting would operate in $O(N \times M)$.

Why it fails: The constraints state that g.length and s.length can be up to $3 \cdot 10^4$. An $O(N \times M)$ approach results in approximately $9 \cdot 10^8$ operations, which generally exceeds the time limit (typically around $10^8$ operations per second). Furthermore, without sorting, a simple greedy pass (e.g., giving the first valid cookie found) is incorrect because it might waste a large cookie on a child with small greed, preventing a solution for a child with higher greed later.

Algorithm Strategy: Greedy Patterns

1. Sort Data: Begin by sorting the greed array g and the cookie size array s in non-decreasing order. This aligns the problem with the sorting-based greedy subpattern.
2. Initialize Pointers: Use two pointers, child_i and cookie_j, both initialized to 0. These track the current child we are trying to satisfy and the current cookie we are considering.
3. Iterate and Match: Traverse through the arrays using a loop that continues as long as both pointers are within bounds.
   • Check if s[cookie_j] >= g[child_i].
   • If true: The cookie satisfies the child. This is a successful assignment. Increment the count of content children (move child_i forward) and mark the cookie as used (move cookie_j forward).
   • If false: The current cookie is too small for the current child. Since the children are sorted, this cookie is also too small for any subsequent child. We must discard this cookie and try the next larger one (move cookie_j forward only).
4. Termination: The process stops when we run out of either children or cookies. The final value of child_i represents the number of satisfied children.

Execution Flow

Let g = [1, 2, 3] and s = [1, 1].

1. Sort:
   • g becomes [1, 2, 3] (already sorted).
   • s becomes [1, 1] (already sorted).
2. State 0: child_i = 0, cookie_j = 0, count = 0.
   • Compare g[0] (1) and s[0] (1).
   • Condition 1 >= 1 is True.
   • Action: Match found. Increment child_i to 1, cookie_j to 1.
3. State 1: child_i = 1, cookie_j = 1.
   • Compare g[1] (2) and s[1] (1).
   • Condition 1 >= 2 is False.
   • Action: Cookie too small. Increment cookie_j to 2.
4. State 2: child_i = 1, cookie_j = 2.
   • cookie_j is now out of bounds (index 2 equals length of s).
   • Loop terminates.
5. Result: Output child_i, which is 1.

Proof of Correctness

We can prove this greedy strategy works via an exchange argument. Suppose there exists an optimal solution $O$ that differs from our greedy solution $G$.

In our greedy solution, we assign the smallest valid cookie $C_{small}$ to the least greedy child $K_{least}$. Suppose the optimal solution $O$ instead assigns a larger cookie $C_{large}$ to $K_{least}$, or assigns $C_{small}$ to a child with higher greed.

1. If $O$ assigns $C_{large}$ to $K_{least}$: We can swap $C_{large}$ with $C_{small}$. Since $C_{large} > C_{small} \ge \text{greed}(K_{least})$, the swap is valid for $K_{least}$. The larger cookie $C_{large}$ is now available for other children, which can only improve or maintain the solution's quality, never degrade it.
2. If $O$ discards $C_{small}$ entirely: We can use $C_{small}$ to satisfy $K_{least}$ instead of whatever cookie $O$ used (or didn't use). This preserves resources for harder-to-satisfy children.

Thus, the greedy choice of "smallest sufficient cookie for smallest greed" never leads to a suboptimal outcome.

Pattern Reuse Notes

The Greedy - Sorting Based pattern used in LeetCode 455 is a fundamental technique for optimization problems involving resource allocation.

• LeetCode 135: Candy: Requires satisfying local constraints (neighbors) with minimum resources. Sorting isn't used directly on the input, but the greedy "two-pass" logic is similar in spirit to establishing a sorted invariant.
• LeetCode 406: Queue Reconstruction by Height: Involves sorting people by height and then inserting them greedily. The sorting step is the critical enabler for the greedy placement.
• LeetCode 1029: Two City Scheduling: We sort by the difference in costs to make the greedy choice of sending people to City A or City B. This perfectly mirrors the strategy of sorting to expose the optimal local choice.

Reference Implementation

C++ Solution for LeetCode 455

1class Solution {
2public:
3    int findContentChildren(vector<int>& g, vector<int>& s) {
4        // Sort both greed factors and cookie sizes
5        sort(g.begin(), g.end());
6        sort(s.begin(), s.end());
7        
8        int child_idx = 0;
9        int cookie_idx = 0;
10        
11        // Iterate while we have both children and cookies left
12        while (child_idx < g.size() && cookie_idx < s.size()) {
13            // If the current cookie satisfies the current child
14            if (s[cookie_idx] >= g[child_idx]) {
15                child_idx++; // Move to the next child
16            }
17            // Always move to the next cookie. 
18            // If it was a match, the cookie is consumed.
19            // If it wasn't, the cookie was too small and is discarded.
20            cookie_idx++;
21        }
22        
23        return child_idx; // The number of children satisfied
24    }
25};

Java Solution for LeetCode 455

1import java.util.Arrays;
2
3class Solution {
4    public int findContentChildren(int[] g, int[] s) {
5        // Sort both arrays to enable greedy matching
6        Arrays.sort(g);
7        Arrays.sort(s);
8        
9        int childIdx = 0;
10        int cookieIdx = 0;
11        
12        // Traverse both arrays
13        while (childIdx < g.length && cookieIdx < s.length) {
14            // Check if current cookie fits current child's greed
15            if (s[cookieIdx] >= g[childIdx]) {
16                childIdx++; // Child is content, move to next child
17            }
18            // Move to next cookie regardless of match status
19            cookieIdx++;
20        }
21        
22        return childIdx;
23    }
24}

Python Solution for LeetCode 455

1class Solution:
2    def findContentChildren(self, g: List[int], s: List[int]) -> int:
3        # Sort both lists in ascending order
4        g.sort()
5        s.sort()
6        
7        child_idx = 0
8        cookie_idx = 0
9        
10        # Iterate until we run out of children or cookies
11        while child_idx < len(g) and cookie_idx < len(s):
12            # If the current cookie is large enough for the current child
13            if s[cookie_idx] >= g[child_idx]:
14                child_idx += 1  # Child is satisfied
15            
16            # Move to the next cookie (either used or too small)
17            cookie_idx += 1
18            
19        return child_idx