Assign Cookies

Q: What is the time complexity of Assign Cookies?

Sorting the two arrays costs O(n log n + m log m) , and the two pointer walk after it is O(n + m) , so the sorts dominate. Sorting in place keeps the extra space at O(1) , apart from what the sort itself uses.

Q: Why does the greedy choice work for Assign Cookies?

Let k be the smallest cookie that fits the least greedy child, and suppose a best assignment gives that child another cookie. Swap: the child takes k , and whoever had k takes the other cookie, which is at least as big, so both stay fed. The count does not change, and the argument repeats for the rest.

EasyGreedy Sorting

+10

Each child i has a greed factor g[i]: the smallest cookie size that makes them happy. Each cookie j has a size s[j]. A child is content when they get one cookie whose size is at least their greed factor. Every child gets at most one cookie and every cookie goes to at most one child. Return the largest number of children you can make content.

Function

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: the greed factor of each child, the smallest cookie size they accept
sinteger-array: the size of each cookie
Returnsinteger: the most children that can each get a cookie at least as big as their greed factor

Constraints

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
The two arrays may have different lengths, and neither is sorted.

Examples

Input: g = [4, 2, 7]s = [3, 5, 1, 2]
Output: 2
Explanation: Sorted, the children want 2, 4 and 7. Cookie 2 feeds the child who wants 2 and cookie 5 the child who wants 4. No cookie reaches 7, so the answer is 2.

Follow-up

What if each child also has a largest cookie they will accept, so a cookie fits only inside a range? Which waiting child should each cookie go to then?

Solution

Trying every pairing of children and cookies explodes, but one greedy rule settles it: serve the least greedy child first, with the smallest cookie that fits. After sorting both arrays, that rule becomes a single walk with two pointers.

Smallest fitting cookie for each child

Correct, but does not finish on the largest tests

Intuition

Take the children from least to most greedy, and give each the smallest unused cookie that is big enough. A bigger cookie feeds every child a smaller one can, so handing out the smallest that works keeps the bigger cookies for the greedier children who come later.

Each of the n children scans all m cookies: with n = m = 5000, that is 25 million checks.

Algorithm

Sort the greed factors from smallest to largest.
Keep a flag for each cookie that says whether it is used.
For each child, scan all cookies and remember the smallest unused one whose size is at least the child's greed.
If you found one, mark it used and count the child as content.
Return the count.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Sort both and use two pointers

Intuition

Sort the cookies too, and you meet the smallest fitting cookie first. Walk the cookies from smallest to largest with one pointer, child, at the least greedy child still waiting. A cookie of at least g[child] feeds that child and moves the pointer. A smaller cookie is also smaller than every waiting child's greed, so it is useless.

In the first example cookie 1 is too small for 2, cookie 2 feeds the child who wants 2, cookie 3 is too small for 4, and cookie 5 feeds the child who wants 4. The pointer stops at 2.

Each pointer only moves forward, so the walk is O(n + m) and the two sorts dominate.

Algorithm

Sort g and s in increasing order.
Set child = 0, the least greedy child still waiting.
For each cookie, smallest first: if child is still inside g and the cookie is at least g[child], add 1 to child.
Return child, the number of children fed.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Pitfalls and edge cases

Handing a child a bigger cookie than they need. With g = [1, 2] and s = [1, 3], giving cookie 3 to the child who wants 1 leaves the child who wants 2 hungry.
Advancing the child pointer when a cookie is too small. The child still needs a cookie; it is the cookie that is useless.
Skipping the bound check on the child pointer. With g = [1] and s = [1, 2], cookie 2 reads past the end of g.
Comparing with > instead of ≥. A cookie exactly the size of the greed factor is enough.
Sorting numbers as text. In JavaScript, sort() without a comparator puts 10 before 9.

Frequently asked questions3

What is the time complexity of Assign Cookies?

Sorting the two arrays costs O(n log n + m log m), and the two pointer walk after it is O(n + m), so the sorts dominate. Sorting in place keeps the extra space at O(1), apart from what the sort itself uses.

Why does the greedy choice work for Assign Cookies?

Let k be the smallest cookie that fits the least greedy child, and suppose a best assignment gives that child another cookie. Swap: the child takes k, and whoever had k takes the other cookie, which is at least as big, so both stay fed. The count does not change, and the argument repeats for the rest.

Can you start from the greediest child instead?

Yes. Sort both arrays and walk from the biggest cookie and the greediest child. If the biggest cookie left fits the greediest child left, feed them and move both pointers; if not, no cookie can feed that child, so skip it. It gives the same count in the same time.

def findContentChildren(g, s):
    # Write code here

Test #1

Test #2

Arguments

g = [4, 2, 7]
s = [3, 5, 1, 2]

Expected Output