L1. Assign Cookies | Greedy Algorithm Playlist

This chapter introduces the fundamental mechanics of Greedy Algorithms by solving the classic "Assign Cookies" problem. We explore how making locally optimal choices at each step leads to a globally optimal solution—maximizing the number of satisfied children given a limited set of cookie sizes.

1. Problem Statement: The Cookie Distribution Challenge

Imagine you are a parent with $n$ children and $m$ cookies.

• Each child has a greed factor ($g[i]$), which represents the minimum cookie size required to satisfy them. For instance, a child with a greed factor of $3$ will only be happy if given a cookie of size $3$ or greater.
• Each cookie has a size ($s[j]$).
• Rule: You can give at most one cookie to one child. A cookie cannot be split or reused.
• Goal: Maximize the total number of children who receive a cookie and are satisfied. You only need to return the count of satisfied children, not their specific identities.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Restaurant and Budget Matching

Analogy: Imagine you are managing a fixed budget of cash bills (cookies) to satisfy customers (children) who have varying minimum spending requirements (greed factors). If a customer only needs $1 to be happy, you don't hand them a \char36 100 bill; you give them the smallest possible bill that meets or exceeds their requirement (\char36 1 or $2). By keeping larger bills in reserve, you preserve your capacity to satisfy customers with much higher demands later on.

• The Greedy Philosophy: Never waste a large resource on a small demand if a smaller resource can suffice. Save the big resources for big demands.

3. Naive vs. Better Approach

The Naive Approach (Exhaustive Search)

• Trying every possible permutation of assigning cookies to children results in an exponential time complexity ($O(n!)$ or $O(2^m)$).
• This approach is entirely unfeasible for large inputs and fails to leverage the ordering properties of the data.

The Better Approach (Greedy Matching with Sorting)

• Insight: Sort both the children's greed factors and the cookie sizes in ascending order.
• Use a two-pointer technique to iterate through both arrays simultaneously. Match the smallest available cookie to the child with the smallest possible greed factor that the cookie can satisfy.

4. Step-by-Step Evolution of the Algorithm

Let's trace a concrete example to understand how the pointer logic operates.

• Greed Array (grid): [1, 3, 3, 4, 5] (Sorted)
• Size Array (size): [1, 1, 2, 2, 3] (Sorted)

Execution Trace:

1. Pointers setup:
   • L (pointing to cookies, index 0)
   • R (pointing to children, index 0)
2. Comparison 1: Cookie size 1 vs. Child greed 1.
   • Since size[L] >= grid[R] (1 >= 1), the child is satisfied!
   • Move both pointers: L moves to index 1, R moves to index 1.
3. Comparison 2: Cookie size 1 vs. Child greed 3.
   • size[L] (1) is less than grid[R] (3). The cookie is too small for this child.
   • Advance only the cookie pointer L to look for a larger cookie.
4. Continuing the Walkthrough:
   • We continue evaluating cookies against the child's greed.
   • Whenever size[L] >= grid[R], we increment both L and R (child satisfied).
   • Whenever size[L] < grid[R], we increment only L (cookie too small, discard it).
5. Termination: The loop terminates when we run out of cookies (L reaches the end of the size array).

5. Visual Flow Walkthrough

6. Complete Code Implementation

Here is the clean, production-ready implementation of the algorithm in Java (mirroring the logic taught in the lecture):

import java.util.Arrays;

public class Solution {
    public int findContentChildren(int[] grid, int[] size) {
        int n = grid.length;
        int m = size.length;

        // Step 1: Sort both greed and size arrays in ascending order
        Arrays.sort(grid);
        Arrays.sort(size);

        int l = 0; // Pointer for cookies (size array)
        int r = 0; // Pointer for children (grid array)

        // Step 2: Iterate while we have cookies and children left to check
        while (l < m && r < n) {
            // If the current cookie can satisfy the current child's greed
            if (size[l] >= grid[r]) {
                // Satisfy the child, move to the next child
                r++;
            }
            // Regardless of whether the cookie was used or too small, 
            // move to the next available cookie
            l++;
        }

        // The index `r` represents the total number of children satisfied
        return r;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Greedy Paradigm Definition: Making the locally optimal choice at each stage (assigning the smallest sufficient cookie) to achieve a globally optimal outcome (maximizing total satisfied children).
• Prerequisite for Greedy: Sorting is frequently a critical preprocessing step for greedy algorithms, transforming an unstructured search space into an ordered sequence where decisions become trivial.
• Two-Pointer Strategy: Using two independent indices (l for cookies, r for children) allows efficient linear scanning after sorting.
• Handling Mismatches: If a resource (cookie) is too small for a demand (greed factor), discard the resource and move on; never look back.
• State Representation: The final position of the child pointer (r) directly corresponds to the total number of successful matches achieved.