Assign cookies in Python with two pointers

Why this matters

A greedy algorithm makes the choice that looks best at each step and never goes back to change it. Greedy methods solve many real problems: choosing which job runs next, packing items into a box, or picking meeting times. A greedy method only gives the best answer when the choice made at each step cannot hurt the final result. Proving that is part of the work, and this lesson is a case where the proof is short.

The Balloons lesson earlier in this module covers a different greedy problem. This lesson adds a second index that moves through the other list at the same time. That pattern is called two pointers. In this lesson a pointer is just an integer index into a list. It tells you which element you are looking at right now.

The problem in plain words

Imagine a teacher with a box of cookies. Each child has a number called a greed factor. It is the smallest cookie size that child will accept. A child with greed factor 2 is happy with a cookie of size 2 or more, and unhappy with a cookie of size 1. Each child gets at most one cookie, and each cookie goes to at most one child. A child who gets a cookie big enough is a content child. The goal is to make as many children content as possible.

Here is a small case:

• Greed factors of the children: 1, 2, 3
• Sizes of the cookies: 1, 1

Both cookies have size 1, so only the child with greed factor 1 can be content. The answer is 1.

Store the inputs as Python lists. A list is an ordered collection of values, and each value has an index. The first index is 0. The line greed = [1, 2, 3] creates a list of three whole numbers. greed[0] is 1, and greed[2] is 3. Python decides the type of each number from the value you write, so there is no separate line that says "this is a whole number". A Python integer can also be as large as memory allows.

The input may come in any order. The children may be listed in any order, and so may the cookies. A cookie that is too small for one child might be fine for another, so you cannot throw a cookie away the first time it fails.

Start with the least greedy child

The greedy rule for this problem is:

1. Take the child with the smallest greed factor.
2. Find the smallest cookie that satisfies that child.
3. Give that cookie to that child.
4. Move to the next child and repeat.

The reason for the smallest cookie is that a big cookie is worth more than a small one. A big cookie can satisfy almost any child, but a small cookie can only satisfy a few. If the least greedy child takes a big cookie when a small one would work, the big cookie is wasted. Later children may then have nothing that fits them.

Here is a worked example with two children and two cookies. The children have greed factors 1 and 3. The cookies have sizes 1 and 3.

Option A: give the size 3 cookie to the greed 1 child. The greed 3 child then gets the size 1 cookie, which is too small. Result: 1 content child.

Option B: give the size 1 cookie to the greed 1 child. The greed 3 child gets the size 3 cookie, which is big enough. Result: 2 content children.

The greedy rule chooses option B. It gives the least greedy child the smallest cookie that works. That leaves the big cookies for the children who need them.

Sort both lists

To find the smallest cookie that works for each child, you could scan all the cookies every time. Sorting removes that repeated search. After sorting, the children run from least greedy to most greedy, and the cookies run from smallest to biggest.

The built-in function sorted(items) returns a new list in order and leaves the original list as it was. The method items.sort() changes the list it is called on. The code below uses sorted, so the caller's lists keep their original order without any extra copy step. The mistakes section shows what items.sort() does to a caller's list.

The two-pointer walk

The walk uses two index variables:

• child points at the least greedy child who is not yet content.
• cookie points at the smallest cookie not yet looked at.

Each step compares s[cookie] with g[child], where g is the sorted greed factors and s is the sorted sizes.

• If the cookie is big enough, the child is content. Move child forward to the next child. The cookie is now used.
• If the cookie is too small, skip it.

Either way, move cookie forward. A used cookie is never used again. A skipped cookie can be dropped for good. Here is why a skipped cookie is safe to drop. The cookie is too small for the least greedy waiting child. Every other waiting child has a greed factor that is the same or bigger, so the cookie is too small for them too. No later child could use it.

The walk stops when either pointer reaches the end of its list. The value of child at the end is the number of content children.

Here is the full program. Read the loop first, then the output.

Save the file and run it with python3 file.py. The output is:

1
2
2
4

The type hints list[int] and -> int describe the types for people and editors. Python does not check them when the program runs.

Notice that cookie += 1 runs on every pass of the loop, while child += 1 runs only when the cookie fits. Each cookie is looked at exactly once.

Worked example 1: one cookie is too small

The greed factors are 1, 2 and 3. The sizes are 1 and 1. The trace below shows each decision. It comes from a copy of the same loop with a print line added in each branch. The program is not part of the code above.

cookie 0 (size 1) fits child 0 (greed 1)
cookie 1 (size 1) too small for child 1 (greed 2), skip
result = 1

The first cookie is used. The second cookie is too small for the child who needs 2, so it is skipped. The child who needs 3 never gets a look, because the cookies ran out.

Worked example 2: every child is fed

Greed factors 1 and 2, sizes 1, 2 and 3. The sizes are already in order, so the walk is simple.

cookie 0 (size 1) fits child 0 (greed 1)
cookie 1 (size 2) fits child 1 (greed 2)
result = 2

The size 3 cookie is never used. It is left over, which is fine. Leftover cookies do not reduce the count.

Worked example 3: small cookies are skipped

Three children all need greed 3. The cookies have sizes 1, 2, 3 and 4. This is harder, because the first two cookies are useless for every child.

cookie 0 (size 1) too small for child 0 (greed 3), skip
cookie 1 (size 2) too small for child 0 (greed 3), skip
cookie 2 (size 3) fits child 0 (greed 3)
cookie 3 (size 4) fits child 1 (greed 3)
result = 2

Two children are content. The third child has no cookie left. The walk skips the small cookies without any cost, because no child could use them.

Worked example 4: unsorted input

The greed factors are 4, 2, 1 and 3, in that order. The sizes are 2, 5, 3, 1 and 7. Sorting gives greed [1, 2, 3, 4] and sizes [1, 2, 3, 5, 7].

cookie 0 (size 1) fits child 0 (greed 1)
cookie 1 (size 2) fits child 1 (greed 2)
cookie 2 (size 3) fits child 2 (greed 3)
cookie 3 (size 5) fits child 3 (greed 4)
result = 4

All four children are content. The size 7 cookie is not needed.

Why the greedy rule is safe

Here is a short argument for why the rule gives the best count. Call the least greedy child C. Two facts are enough.

First, if some cookie fits C, the best answer satisfies C. Suppose the best answer does not satisfy C, but a cookie Z fits C. If Z is unused, giving Z to C raises the count, which contradicts that the answer was best. If Z went to someone else, giving Z to C instead keeps the count the same. Either way, there is a best answer that satisfies C.

Second, the cookie given to C can be the smallest cookie that fits C. Let X be the cookie C gets in that best answer, and let Y be the smallest cookie that fits C. Y is no bigger than X. If Y is unused, swap X for Y, so C keeps a fitting cookie and X is free. If Y went to another child D, give D the cookie X instead. D's greed factor is no bigger than Y, and Y is no bigger than X, so X fits D. The count stays the same.

After C is settled, the same argument applies to the rest of the children with the remaining cookies. The walk does exactly this, one child at a time.

A version with bisect

The standard library module bisect finds a position in a sorted list without a loop. The function bisect_left(items, x) returns the index where x would go, before any equal values. This gives a second way to find the smallest cookie that fits. For each child, in order, it finds the first cookie that is big enough and removes it from the list.

from bisect import bisect_left
 
 
def content_children_bisect(greed: list[int], sizes: list[int]) -> int:
    available = sorted(sizes)
    count = 0
    for need in sorted(greed):
        index = bisect_left(available, need)
        if index < len(available):
            available.pop(index)
            count += 1
    return count

Running it on the unsorted input from worked example 4 gives the same answer:

4

This version is simpler to read, but pop(index) moves every later item one place left, so it does more work on long lists. The two-pointer walk uses each cookie once and never removes anything, so it is the version to learn first.

Checking the answer with a brute force search

A brute force search tries every way of handing out cookies and keeps the best count. It is too slow for large inputs, but it is a trustworthy judge for small ones. The function below does that search. best handles one child at a time. For that child it tries giving no cookie, and then it tries each cookie that is still free and big enough. For each choice it asks the same question about the next child, and it keeps the largest count it finds.

def brute_force(greed: list[int], sizes: list[int]) -> int:
    def best(i: int, used: frozenset) -> int:
        if i == len(greed):
            return 0
        result = best(i + 1, used)
        for c in range(len(sizes)):
            if c not in used and sizes[c] >= greed[i]:
                result = max(result, 1 + best(i + 1, used | {c}))
        return result
    return best(0, frozenset())

The set used holds the indexes of cookies already given. A frozenset cannot be changed, so each choice builds a new set with used | {c}. The old set is untouched, which means there is nothing to undo when the function steps back. The Java version of this search changes a shared array and then changes it back, and the Python version avoids that step.

To test the walk, a short program made 3000 random cases. Each case had up to 5 children and up to 6 cookies, with greed factors and sizes from 1 to 5. The program compared content_children and content_children_bisect with brute_force for each case, using this code:

import random
 
rng = random.Random(3)
mismatches = 0
for _ in range(3000):
    greed = [rng.randint(1, 5) for _ in range(rng.randint(0, 5))]
    sizes = [rng.randint(1, 5) for _ in range(rng.randint(0, 6))]
    expected = brute_force(greed, sizes)
    if content_children(greed, sizes) != expected:
        mismatches += 1
    if content_children_bisect(greed, sizes) != expected:
        mismatches += 1
print(f"random checks: 3000, mismatches: {mismatches}")

The output was:

random checks: 3000, mismatches: 0

This is evidence, not a proof. The argument in the section above is the proof. The test is a second check that the argument was applied correctly, because a bug in the walk would show up as a mismatch on some small case.

Common mistakes

Forgetting to sort

The walk depends on the lists being in order. Without sorting, the same two-pointer loop gives a smaller count. Take greed factors [1, 3] and sizes [3, 1]. Run the walk on them unsorted, then sort both lists and run it again. The unsorted walk gives 1. The cookie of size 3 satisfies the child who needs 1, and the cookie of size 1 is then too small for the child who needs 3. Sorting first gives 2. The walk function sorts its inputs itself, so this check uses a copy of the loop without the sorting step:

def walk_no_sort(greed: list[int], sizes: list[int]) -> int:
    child = 0
    cookie = 0
    while child < len(greed) and cookie < len(sizes):
        if sizes[cookie] >= greed[child]:
            child += 1
        cookie += 1
    return child
 
 
print("Without sorting:", walk_no_sort([1, 3], [3, 1]))
print("Sorted order:", walk_no_sort(sorted([1, 3]), sorted([3, 1])))

The output is:

Without sorting: 1
Sorted order: 2

Giving each child the biggest cookie that fits

A tempting shortcut is to give the least greedy child the biggest cookie that fits, instead of the smallest. It feels generous, but it wastes big cookies. Take greed factors 1 and 2, and cookie sizes 1 and 3. The least greedy child can take either cookie. If they take the size 3 cookie, the child who needs 2 is left with only the size 1 cookie, which is too small. The count is 1. If the least greedy child takes the size 1 cookie, the other child takes the size 3 cookie, and the count is 2. A short program that picks the biggest fit for each child prints this:

def biggest_fit(greed: list[int], sizes: list[int]) -> int:
    sizes = sorted(sizes)
    count = 0
    for need in sorted(greed):
        fits = [c for c in sizes if c >= need]
        if fits:
            sizes.remove(max(fits))
            count += 1
    return count
 
 
print(biggest_fit([1, 2], [1, 3]))

1

The walk from this lesson gives 2 for the same inputs.

Forgetting the bounds check on the cookie

The loop must stop when either index reaches the end of its list. Suppose you check only child < len(g) in the loop condition. Then the loop keeps going after the cookies run out, and s[cookie] asks for a position that is not in the list. Python stops the program with this message:

def no_bounds_check(greed: list[int], sizes: list[int]) -> int:
    g = sorted(greed)
    s = sorted(sizes)
    child = 0
    cookie = 0
    while child < len(g):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1
    return child
 
 
no_bounds_check([1, 2, 3], [1, 1])

The real output is:

Traceback (most recent call last):
  File "/home/chiranjeet/dev/anisha/scratch-offtmp/claude-port-greedy/c12_bounds.py", line 13, in <module>
    no_bounds_check([1, 2, 3], [1, 1])
    ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^
  File "/home/chiranjeet/dev/anisha/scratch-offtmp/claude-port-greedy/c12_bounds.py", line 7, in no_bounds_check
    if s[cookie] >= g[child]:
       ~^^^^^^^^
IndexError: list index out of range

The message says the program asked for a position that is not in the list. The file path in the traceback depends on where you save the file. The fix is the second condition in the while line: cookie < len(s).

Using == where the object check is meant

In Python, == compares values, and is checks whether two names point at the same object. For numbers, this difference can make a test look right on small data and wrong on large data. This snippet compares four numbers in three ways. The numbers come from int(...), so Python builds each one at run time:

a = int("1000")
b = int("1000")
c = int("100")
d = int("100")
print("1000 == 1000 :", a == b)
print("1000 is 1000 :", a is b)
print("100 is 100 :", c is d)

Its output is:

1000 == 1000 : True
1000 is 1000 : False
100 is 100 : True

CPython, the standard Python program, keeps one shared object for integers from -5 to 256, so is gives True for 100. It gives False for 1000, which is a bug that small test data hides. Use ==, >=, or > to compare numbers. Use is only for checks such as x is None.

Passing values of the wrong type

Python does not check types when you call a function. A list that holds a string and a number is accepted by the function call. The error appears later, when the code compares the two kinds of value. Here is a call with a string in the sizes list:

content_children([1, 2], ["a", 2])

The real output is:

Traceback (most recent call last):
  File "/home/chiranjeet/dev/anisha/scratch-offtmp/claude-port-greedy/c12_type.py", line 13, in <module>
    content_children([1, 2], ["a", 2])
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^
  File "/home/chiranjeet/dev/anisha/scratch-offtmp/claude-port-greedy/c12_type.py", line 3, in content_children
    s = sorted(sizes)
TypeError: '<' not supported between instances of 'int' and 'str'

The message says that < cannot compare an integer with a string. The file path in the traceback depends on where you save the file. The error comes from sorting the sizes list, which holds a string. The type hints would have shown the problem to an editor, but Python itself only reports it when the comparison runs. Check the input data before you call the function, or use a type checker such as mypy on the code.

Changing the caller's list

The method items.sort() changes the list it is called on. If the caller reads the list after the call, the values are now in sorted order and the caller's original order is gone. The function sorted avoids this, because it returns a new list. Here is the difference:

values = [3, 1, 2]
result = sorted(values)
print("sorted() returns:", result, "original:", values)
values.sort()
print("list.sort() changes original:", values)

The output is:

sorted() returns: [1, 2, 3] original: [3, 1, 2]
list.sort() changes original: [1, 2, 3]

Practice

Exercise 1. What does content_children return for greed factors [1, 1, 1] and sizes [1, 1, 1, 1]?

Show the answer

It returns 3. Each child takes one of the size 1 cookies, and the fourth cookie is left over.

Exercise 2. Greed factors [5, 6] and sizes [4, 7]. What does it return?

Show the answer

It returns 1. The size 4 cookie is too small for the child who needs 5, so the walk skips it. The size 7 cookie satisfies that child. The child who needs 6 gets nothing because no cookies remain.

Exercise 3. In the content_children function, change >= to >. For greed factors [1, 2] and sizes [1, 2], what does it return?

Show the answer

It returns 1. With >, a cookie of size 2 does not satisfy a child with greed factor 2, because 2 is not bigger than 2. The answer was checked by running a copy of the loop with >.

Exercise 4. Greed factors [10, 9, 8, 7] and sizes [5, 8, 7, 9, 10, 1]. What does it return?

Show the answer

It returns 4. After sorting, the sizes are 1, 5, 7, 8, 9, 10 and the greed factors are 7, 8, 9, 10. The walk skips the cookies of size 1 and 5. The cookies of size 7, 8, 9 and 10 each satisfy the child with the same greed factor.

Exercise 5. Greed factors [] (no children) and sizes [1, 2]. What does it return, and why?

Show the answer

It returns 0. The while condition is false on the first check because child < len(g) is 0 < 0. The loop never runs, so child stays 0.

Summary

• Sort the greed factors and the cookie sizes before the walk, with sorted().
• Use two index variables. Move the cookie index on every step, and move the child index only when a cookie fits.
• A cookie too small for the least greedy waiting child is too small for every later child, so it can be dropped.
• Sorting takes most of the time. The walk itself looks at each element once.