Assign Cookies

How it works

This is a cleaner version of the two-pointer approach. We iterate through cookies one by one. For each cookie, if it can satisfy the current child, we move to the next child. Either way, we move to the next cookie. The key insight is that once a child is satisfied, we never revisit them, and we never skip a potentially useful cookie.

Steps

1. Sort both the greed array and the cookie array.
2. Use pointer i for children (starting at 0) and iterate through cookies with j.
3. If the current cookie satisfies the current child (cookie >= greed), increment i.
4. Always increment j to move to the next cookie.
5. Return i, the count of satisfied children.

Complexity

• Time complexity: O(n log n + m log m)
• Space complexity: O(1) or O(n + m) depending on the sorting algorithm.

Where n is the size of the array g and m is the size of the array s.

Things to watch for

Forgetting to Sort Both Arrays

The two-pointer greedy approach only works when both the greed factors and cookie sizes are sorted. Forgetting to sort one of them leads to suboptimal assignments.

Using the Wrong Comparison Operator

A child is satisfied when the cookie size is greater than or equal to the greed factor. Using strict greater-than misses valid matches where the cookie exactly equals the greed.

from typing import List

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        i = j = 0
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                i += 1
            j += 1

        return i

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0;
        for (int j = 0; i < g.size() && j < s.size(); j++) {
            if (g[i] <= s[j]) i++;
        }
        return i;
    }
};