Assign Cookies

"Assign Cookies" is a problem that is a simple yet elegant introduction to greedy algorithms. It asks us to match two lists - one representing the greed of children and the other representing cookie sizes - in a way that maximizes happiness. It’s a great warm-up to practice sorting and thinking about matching strategies in real-world-like scenarios.

Problem Statement

You are given two integer arrays:

• g[i] is the greed factor of the ith child (the minimum size of a cookie that will satisfy them).

• s[j] is the size of the jth cookie.

Each child can get at most one cookie, and each cookie can be given to at most one child.

Return the maximum number of children you can satisfy.

Example 1:

Input: g = [1,2,3], s = [1,1]  
Output: 1  
Explanation: Only the child with greed factor 1 can be satisfied.

Example 2:

Input: g = [1,2], s = [1,2,3]  
Output: 2  
Explanation: Both children can be satisfied with the cookies 1 and 2.

1. Clarify Requirements Before Jumping Into Code

• Can a child receive more than one cookie? → No.

• Can a cookie be given to multiple children? → No.

• Are both arrays sorted? → No, not necessarily.

• What should I return? → The number of satisfied children.

2. Identify the Category of the Question

Like the problem statement suggests, this sounds like a Greedy Algorithm problem, where the goal is to make a series of local, optimal decisions to maximize overall satisfaction.

Common patterns:

• Matching problems

• Two-pointer strategies

• Sorting followed by greedy choice

3. Consider a Brute‑Force Approach to Understand the Problem

For the brute-force option, we could try every possible combination of cookie and child:

• For each child, scan all cookies and find one that satisfies them and hasn’t been used yet.

  
  

Time Complexity: O(n * m)

n = g.length

m = s.length

4. Brainstorm More Solutions

Part of the reason that the brute-force solution is inefficient is because we have to try and match every cookie with every child. But we know that there may be scenarios where there will be cookies that cannot satisfy a particular child. Is there a way we can avoid having to check all of those cookies?

What if we sorted? Should we sort by increasing values or decreasing values?

If we sort by increasing values, that allows us to satisfy the least greedy child first, matching them with the smallest possible cookie. It also means we leave bigger cookies available for greedier children.

If we sort by decreasing values, we're essentially trying to satisfy the most greedy children first. Does that compromise our ability to maximize the number of children who are satisfied? Not really, since each child can only get one cookie. If a cookie is big enough to satisfy a greedy child, it's also big enough to satisfy the less greedy children. And if a cookie is not big enough to satisfy a greedy child, then we just skip that child and find the next child that can be satisfied by that cookie.

(If you know of a scenario where that's not true, let me know in the comments or by sending me a message!)

So which do we choose?

Well, the whole idea of a greedy algorithm is to try and make the optimal local decision, and it makes more sense to try and satisfy the least greedy children first with the smallest possible cookies.

So what does that look like?

• Sort both array by increasing values: i.e. smallest greed first, smallest cookies first.

• We'll have one pointer i for children, and one pointer j for cookies.

• If s[j] >= g[i], it means we can satisfy child i, so we move both pointers forward.

• Otherwise, we move only j to try the next bigger cookie.

This gives us a runtime of O(n log n) + O(m log m) to sort each array.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute Force	O(n * m)	O(n + m)	Easy to understand	Too slow for large inputs
Sort + Two Pointers (Optimal)	O(n log n + m log m)	O(1) or O(n + m)	Fast, intuitive after sorting	Requires sorting upfront

6. Write Pseudocode to Structure Your Thoughts

sort g
sort s
i, j = 0, 0
while i < g.length and j < s.length:
    if s[j] >= g[i]:
        i += 1
    j += 1
return i

7. Consider Edge Cases

• Empty greed array → return 0

• Empty cookie array → return 0

• All cookies too small → return 0

• Cookies exactly match greed → max matches

8. Write Full Code Syntax (Java)

import java.util.Arrays;

public class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }
        return i;
    }
}

9. Test Your Code

System.out.println(findContentChildren(new int[]{1, 2, 3}, new int[]{1, 1})); // 1  
System.out.println(findContentChildren(new int[]{1, 2}, new int[]{1, 2, 3})); // 2  
System.out.println(findContentChildren(new int[]{5, 10}, new int[]{1, 2, 3})); // 0  
System.out.println(findContentChildren(new int[]{1, 2, 3}, new int[]{3, 2, 1})); // 3  
System.out.println(findContentChildren(new int[]{1}, new int[]{2})); // 1  

10. Key Lessons to Remember for Future Questions

• When matching resources to needs, your first thought should be to sort both arrays and use a greedy matching strategy.

• Think about who is easier to satisfy - start with them.

• Two-pointer approaches work well when two sorted lists need to be matched in order.

• This problem is a great introduction to greedy logic and appears in similar forms across many matching-style interview questions.

Good Luck and Happy Coding!