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. Suppose a best assignment gives that child some other cookie. Swap: the child takes k , and whoever had k takes the other cookie, which is at least as big as k , so they stay fed. The count does not change, so a best assignment can always start with the greedy choice, and the same argument repeats for the remaining children and cookies.

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 and the cookies are 1, 2, 3 and 5. Cookie 2 feeds the child who wants 2 and cookie 5 feeds the child who wants 4. Nothing is left that reaches 7, so the answer is 2.

+16 hidden tests on Submit

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

The question is which child should get which cookie. Trying every pairing explodes, but one greedy rule settles it: serve the least greedy child first, and give them 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 the least greedy to the most greedy. For each one, look through every cookie that is still unused and pick the smallest one that is big enough. If no cookie fits, that child stays hungry. In the first example the children want 2, 4 and 7: the child who wants 2 gets cookie 2, the child who wants 4 gets cookie 5, and nothing is left for 7.

Why the smallest fitting cookie? A bigger cookie can feed every child the smaller one can, and more. Handing out the smallest one that works keeps the bigger cookies for the greedier children who come later, so you never lose a child you could have fed.

The cost is the search. Each of the n children scans all m cookies, so with n = m = 5000 that is 25 million checks, too slow for the largest tests.

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

The scan above looks for the smallest cookie that fits, again and again. Sort the cookies too, and that search disappears: the cookies come in increasing size, so you meet the smallest fitting cookie first.

Walk the cookies from smallest to largest and keep one pointer, child, at the least greedy child still waiting. If the cookie is at least g[child], that child is fed and the pointer moves to the next child. If it is smaller, it is smaller than every child still waiting too, since they are sorted, so the cookie is useless and you move on.

In the first example the sorted cookies are 1, 2, 3, 5 and the sorted greeds are 2, 4, 7. Cookie 1 is too small for 2. Cookie 2 feeds the child who wants 2. Cookie 3 is too small for 4. Cookie 5 feeds the child who wants 4. The pointer stops at 2, the answer.

Each pointer only moves forward, so the walk is O(n + m) and the two sorts dominate. Sorting in place needs no extra arrays.

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

Most wrong answers come from matching in the wrong order or from moving the wrong pointer.

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, while the right pairing feeds both.
Advancing the child pointer when a cookie is too small. The child still needs a cookie; it is the cookie that is useless.
Forgetting the bound check on the child pointer. Once every child is fed, the remaining cookies must not read 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 questions4

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. Suppose a best assignment gives that child some other cookie. Swap: the child takes k, and whoever had k takes the other cookie, which is at least as big as k, so they stay fed. The count does not change, so a best assignment can always start with the greedy choice, and the same argument repeats for the remaining children and cookies.

Can you start from the greediest child instead?

Yes. Sort both arrays, then walk from the biggest cookie and the greediest child: if the biggest cookie left fits the greediest child left, feed them both and move both pointers; if not, that child cannot be fed by any cookie, so skip the child. It gives the same count in the same time.

Is Assign Cookies a dynamic programming problem?

No. A swap argument shows the greedy choice is always safe, so sorting plus one walk is enough, in O(n log n + m log m). A table over the two sorted arrays, filled like a longest common subsequence table, also finds the answer, but it costs O(n × m) time for the same result.

Python

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

Test cases

Case 1

Case 2

Input

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

Expected