Assign Cookies — LeetCode 455 Greedy Two-Pointer Solution

Problem Statement#

Each child has a greed factor and each cookie has a size. A child is satisfied when given a cookie at least as big as their greed. Return the maximum number of satisfied children.

Constraints:

• 1 <= g.length <= 3 * 10^4
• 0 <= s.length <= 3 * 10^4
• 1 <= g[i], s[j] <= 2^31 - 1

Input:  g = [1,2,3], s = [1,1]
Output: 1

Input:  g = [1,2], s = [1,2,3]
Output: 2

Why This Problem Matters#

Assign Cookies is the canonical introductory greedy interview question at Google, Amazon, and TikTok. It's used as a warm-up because anyone can brute-force it but only candidates who articulate the exchange argument prove they understand greedy. The problem looks like an Easy, but the follow-up is "prove your strategy is optimal" — a classic FAANG twist.

The pattern of "sort both arrays and walk two pointers" is reused in Boats to Save People, Two City Scheduling, and many matching problems. Recruiters love it because the code is six lines but the explanation reveals depth.

This pattern also seeds your intuition for harder greedy problems where you must prove no better assignment exists. If you can clearly explain Assign Cookies, you can scaffold the same explanation for harder problems like Task Scheduler or Reorganize String.

The Core Insight#

Greedy choice: give each child the smallest cookie that still satisfies them. Sort both arrays ascending. For the smallest unmet child, hand them the smallest cookie that fits; if no cookie fits, that child cannot be satisfied at all.

Exchange argument: assume an optimal solution gives child A a bigger cookie than necessary while leaving child B (who needs less) unsatisfied. Swap the cookies — child A is still satisfied (smaller cookie still meets their greed), and now child B is also satisfied. The swap never decreases the count, so greedy is optimal.

Visual Dry Run#

For g = [1,2,3], s = [1,1]: child 0 takes cookie 0 (count=1). Child 1 needs 2 but cookie 1 is size 1; advance only the cookie pointer — runs out. Answer = 1.

Solution (Optimal)#

class Solution:
    def findContentChildren(self, g, s):
        g.sort()
        s.sort()
        i = j = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1
            j += 1
        return i

var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    let i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) i++;
        j++;
    }
    return i;
};

Time: O(n log n + m log m) — sorting dominates, traversal is O(n + m) Space: O(1) extra besides the in-place sort

Common Mistakes#

• Sorting only one array and trying to match with a hash map — overcomplicates an O(n log n) problem
• Advancing the child pointer when a cookie does not fit — you skip a child who could be satisfied by a later cookie
• Using descending order without flipping the comparison — produces the wrong assignment
• Returning j instead of i — j counts cookies tried, not children satisfied

Interview Tips#

• Lead with the exchange argument before writing code — interviewers value the proof
• Mention the runtime is bounded by sorting, not the linear walk
• Note this is the same pattern as Two City Scheduling and Boats to Save People

Follow-up Questions#

• What if each cookie can satisfy more than one child? Hint: split cookie greedily by greed
• What if children have utility values and you maximize total utility? Hint: this becomes assignment, no longer pure greedy
• What if cookies must go to the youngest unmet child? Hint: still greedy on the sorted indices
• What if you can break a cookie? Hint: fractional knapsack
• What if children come in a stream? Hint: maintain a sorted multiset of unused cookies

Key Takeaways#

• LeetCode 455 Assign Cookies is the entry-level greedy interview question at Google and Amazon
• Sort both arrays ascending and use two pointers for an O(n log n) solution
• The greedy choice "smallest cookie that satisfies" is provable by exchange argument
• Advance only the cookie pointer on a mismatch, both on a match
• Runtime is dominated by sort; traversal is linear
• Same template applies to Boats to Save People, Two City Scheduling, and similar pairing problems
• Always state the invariant — "matched children form a prefix of sorted g" — during the interview