Understanding Assign Cookies in Java

Introduction & Problem Explanation

If you are looking for a straightforward introduction to greedy algorithms, the Assign Cookies problem is a great place to start. The setup is simple: you have a group of children and a collection of cookies. Each child has a specific "greed factor"—the minimum cookie size they need to be happy. Each cookie also has a specific size. Your goal is to distribute the cookies to satisfy as many children as possible. However, there are two constraints: you can only give a child one cookie, and they won't accept any cookie smaller than their greed factor.

Let's look at a quick example:

• Children's greed factors: g = [1, 2, 3]
• Cookie sizes: s = [1, 1]

Here, we have three children demanding sizes 1, 2, and 3, but we only have two cookies, both of size 1. We can easily satisfy the first child (greed 1) with either cookie, but the remaining children require larger cookies than what we have left. Thus, the maximum number of content children we can satisfy is 1.

The Algorithmic Approach

Two-Pointer Greedy Search (O(n log n) Time, O(1) Space)

This is a classic candidate for a greedy algorithm. The core intuition is simple: to make the most children happy, we should avoid giving large cookies to kids with small appetites. Saving larger cookies for kids with higher greed factors gives us the best chance of satisfying them later. Here is the plan:

1. Sort both groups: Sort the children's greed factors (g) and the cookie sizes (s) in ascending order.
2. Track with two pointers: Start with two pointers at the beginning of each array (e.g., child = 0 and cookie = 0).
3. Walk through the arrays: We loop while child < g.length and cookie < s.length:
   • If the current cookie is big enough for the current child (s[cookie] >= g[child]), we make a match. We move the child pointer forward to focus on the next kid.
   • Whether the cookie was a match or too small, we always move the cookie pointer forward. If a cookie is too small for the current child (who has the lowest greed among the remaining children), it won't satisfy any of the other children either.

Sorting takes O(n log n + m log m) time, and the two-pointer loop runs in linear O(n + m) time.

Step-by-Step Execution Walkthrough

Let's trace this with a simple test case:

• Children greed: g = [1, 2]
• Cookie sizes: s = [1, 2, 3]

After sorting (they are already sorted), we start both pointers at index 0:

1. Iteration 1: The cookie size is 1 and the child's greed is 1. Since 1 >= 1, we have a match! We satisfy the first child, so both pointers move to index 1.
2. Iteration 2: The cookie size is 2 and the child's greed is 2. Since 2 >= 2, we have another match! We satisfy the second child. Both pointers increment again.
3. Termination: The child pointer reaches the end of the array. We stop and return 2, representing the number of satisfied children.

Key Code Snippets & Explanations

Let's look at the key details of the code logic:

• Arrays.sort(g); Arrays.sort(s);: Sorting both inputs guarantees we are always matching the smallest requirements with the smallest resources first.
• if (s[cookie] >= g[child]) child++;: Checks if the cookie is large enough. If it is, child++ marks that child as satisfied and ready for the next one.
• cookie++;: Ensures we move on to the next cookie in every step. Since we sorted the arrays, a cookie that fails to satisfy the current child is too small for anyone else and can be safely skipped.

Java Implementation Code

Here is the complete Java implementation of this solution. The main method includes a test run so you can see it in action.

package io.practise.dsa;

import java.util.Arrays;

public class AssignCookies {

    // Sorting & Two Pointers: Time O(N log N + M log M), Space O(1)
    public int findContentChildren(int[] g, int[] s) {
        if (g == null || s == null) {
            return 0;
        }

        // Sort children greed and cookie sizes
        Arrays.sort(g);
        Arrays.sort(s);

        int child = 0;
        int cookie = 0;

        // Try matching the smallest greed with the smallest sufficient cookie
        while (child < g.length && cookie < s.length) {
            if (s[cookie] >= g[child]) {
                child++; // Successfully satisfied this child, move to next child
            }
            cookie++; // Move to evaluate the next cookie
        }

        return child;
    }

    public static void main(String[] args) {
        AssignCookies solver = new AssignCookies();
        int[] g = {1, 2, 3}; // Greed factors of children
        int[] s = {1, 1};    // Cookie sizes

        System.out.println("--- Assign Cookies Demonstration ---");
        System.out.println("Children Greed Factors: " + Arrays.toString(g));
        System.out.println("Available Cookie Sizes: " + Arrays.toString(s));
        int contentChildren = solver.findContentChildren(g, s);
        System.out.println("Maximum satisfied children: " + contentChildren); // Expected: 1
    }
}

Conclusion

The Assign Cookies problem demonstrates how a greedy strategy can yield an optimal global result by making optimal local decisions. By sorting the data, we align our resources with our requirements, satisfying the maximum number of children without wasting larger cookies.