Assign cookies 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. Many everyday programming tasks have this shape. You have a set of items and a set of people, and each person can take one item if it fits their need. Giving out seats, matching drivers to rides and assigning jobs to free workers all follow the same pattern.

This lesson uses one small matching problem to show the pattern. The method is simple: sort both lists, then walk through them once with two pointers. Once you can explain why that works, you can apply the same thinking to bigger problems.

You need to know std::vector and for loops. Sorting is explained here from the start. The next lesson in this module, candy distribution, also scans a list in order, but it needs two passes instead of one.

The problem in plain words

Picture a teacher giving out cookies to a class. Each child has a number called a greed value. It is the smallest cookie size that child will accept. A child with greed value 2 is happy with a cookie of size 2 or 3, but not with a cookie of size 1.

Two rules apply:

• Each child takes at most one cookie.
• Each cookie goes to at most one child.

The goal is to make as many children happy as possible. The answer is a count, not a list of who got what.

Here is a tiny case you can work out by hand. The children need 1, 2 and 3. There are two cookies, both of size 1. Only the child who needs 1 can be happy, because the other cookies are too small for the other two children. The answer is 1.

Two terms are used in this lesson:

• Sorting means putting a list in order, usually from smallest to largest. std::sort does this in C++.
• Two pointers means two index variables. Each one holds a position in a list and moves forward. It does not mean the raw pointer type int*. Here, a pointer is just a position number.

The greedy idea

The method has two steps.

1. Sort the children by need, smallest need first.
2. Sort the cookies by size, smallest first.

Then go through the children in that order. For each child, look for the smallest cookie that is big enough. If a cookie is too small for the current child, skip it. Give the chosen cookie to the child and move on to the next child.

Why is it safe to give each child the smallest big-enough cookie? Consider the least needy child who is still waiting. Any cookie that is too small for that child is too small for every other waiting child too, because they need more. So skipping it costs nothing. And if the smallest big-enough cookie went to someone else, you could swap it with the cookie that this child received. Nobody ends up worse off. The greedy choice never blocks a better choice.

The idea of skipping cookies that are too small is what makes the cookie position move only forward. You never need to go back.

Worked example 1: one cookie for two children

Take the children {1, 2, 3} and the cookies {1, 1}. Sort both lists. They are already sorted here, so nothing changes.

Trace the walk by hand:

Cookie index 0 (size 1), child needing 1: 1 is at least 1, so give it. Count = 1.
Cookie index 1 (size 1), child needing 2: 1 is less than 2, so skip it.
No cookies left. Stop.
Answer: 1

Notice that the second cookie was skipped for the child who needed 2. It was also too small for the child who needed 3, so it was never useful. The walk stops when the cookies run out.

Writing the loop in C++

The C++ code below walks both sorted lists at once. cookie is the position in the sorted cookie list. The loop variable need takes each child's value in sorted order. The function returns the matches it made, as a list of pairs. A pair holds two values side by side. Here the first value is the child's need and the second is the cookie size.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
 
using Match = std::pair<int, int>;  // (child's need, cookie size)
 
std::vector<Match> assignCookies(std::vector<int> greed, std::vector<int> cookies) {
    std::sort(greed.begin(), greed.end());
    std::sort(cookies.begin(), cookies.end());
 
    std::vector<Match> matches;
    std::size_t cookie = 0;
    for (int need : greed) {
        while (cookie < cookies.size() && cookies[cookie] < need) {
            ++cookie;
        }
        if (cookie == cookies.size()) {
            break;
        }
        matches.emplace_back(need, cookies[cookie]);
        ++cookie;
    }
    return matches;
}
 
void show(const std::vector<int>& greed, const std::vector<int>& cookies) {
    auto matches = assignCookies(greed, cookies);
    std::cout << "content children: " << matches.size() << '\n';
    for (auto [need, size] : matches) {
        std::cout << "  needs " << need << " gets " << size << '\n';
    }
}
 
int main() {
    std::cout << "Example 1\n";
    show({1, 2, 3}, {1, 1});
    std::cout << "Example 2\n";
    show({1, 2}, {1, 2, 3});
    std::cout << "Example 3\n";
    show({1, 4, 6}, {2, 3, 5, 9});
    std::cout << "Example 4\n";
    show({10, 9, 8, 7}, {5, 6, 7, 8});
    std::cout << "Example 5 (no cookies)\n";
    show({1}, {});
}

Compile and run it:

g++ -std=c++20 -Wall -o cookies cookies.cpp
./cookies

The output is:

Example 1
content children: 1
  needs 1 gets 1
Example 2
content children: 2
  needs 1 gets 1
  needs 2 gets 2
Example 3
content children: 3
  needs 1 gets 2
  needs 4 gets 5
  needs 6 gets 9
Example 4
content children: 2
  needs 7 gets 7
  needs 8 gets 8
Example 5 (no cookies)
content children: 0

A few details in the code are worth knowing.

The first two lines of the function sort the copies of the lists. The function takes its inputs by value, so the caller's vectors are not changed. Sorting the copies is safe.

The while loop skips cookies that are too small. It stops at the first cookie that is big enough, or at the end of the list. The if after it checks which case happened. If the end was reached, no cookie is left for this child or any child after them, so the loop stops with break.

The variable cookie is of type std::size_t. This is the unsigned integer type that C++ uses for container sizes and positions. Using it for positions keeps the comparison with cookies.size() clean. The mistakes section shows what goes wrong when it is not used.

Worked example 2: children who go without

Example 4 in the program has children who need {10, 9, 8, 7} and cookies {5, 6, 7, 8}. Sorted, the children need 7, 8, 9 and 10. The cookies, sorted, are 5, 6, 7 and 8.

Walk through it:

Need 7: skip 5 (too small), skip 6 (too small), 7 is big enough. Give 7. Count = 1.
Need 8: next cookie is 8. Give 8. Count = 2.
Need 9: no cookies left. Stop.

The children needing 9 and 10 go without. The answer is 2. The walk showed that the greedy rule gives the smallest cookie to the least needy child first. That leaves larger cookies for the children who need more. In this case there was not enough cookie size to satisfy everyone, so the answer stops at 2.

Worked example 3: a skipped cookie that stays unused

Example 3 has children who need {1, 4, 6} and cookies {2, 3, 5, 9}. Sorted, the lists are unchanged. Walk through them:

Need 1: cookie 2 is big enough. Give 2. Count = 1.
Need 4: cookie 3 is too small, skip it. Cookie 5 is big enough. Give 5. Count = 2.
Need 6: cookie 9 is big enough. Give 9. Count = 3.

The cookie of size 3 was skipped for the child who needed 4, and it was never needed later. The answer is 3. The output of the program confirms each match.

The skip is the important part. The children are sorted, so every child after the current one needs at least as much. A cookie that is too small for the current child is therefore too small for every child who has not been matched yet. That is why the cookie index never needs to move back.

Worked example 4: six children and five cookies

The last example is larger, so you can see the same steps run many times. The children need {5, 3, 8, 1, 4, 9} and the cookies are {7, 2, 6, 3, 10}. Sort both lists first. The children become 1, 3, 4, 5, 8, 9. The cookies become 2, 3, 6, 7, 10.

Walk through the sorted lists:

Need 1: cookie 2 is big enough. Give 2. Count = 1.
Need 3: cookie 3 is big enough. Give 3. Count = 2.
Need 4: cookie 6 is big enough. Give 6. Count = 3.
Need 5: cookie 7 is big enough. Give 7. Count = 4.
Need 8: cookie 10 is big enough. Give 10. Count = 5.
Need 9: no cookies left. Stop.

Calling show({5, 3, 8, 1, 4, 9}, {7, 2, 6, 3, 10}) prints:

content children: 5
  needs 1 gets 2
  needs 3 gets 3
  needs 4 gets 6
  needs 5 gets 7
  needs 8 gets 10

The child who needs 9 is the only one left without a cookie. Every cookie was used in order, and none was skipped for a child who could have used it. That is the usual shape of a good result for this method.

Checking an answer by hand

Three checks catch most mistakes in a list of matches. Use them on paper before you trust a result.

• Each cookie must be at least as big as the need of the child it went to.
• No cookie appears twice in the matches.
• The answer must equal the number of matches.

Take the matches from Example 3: child needing 1 with cookie 2, child needing 4 with cookie 5, and child needing 6 with cookie 9. The cookies are 2, 5 and 9. Each one is at least the need beside it. The three cookies are different sizes, so none is used twice. There are three matches, and the answer is 3.

Why the walk is fast

The method has two costs. The first is the sort. Sorting a list takes time that grows a little faster than the length of the list, roughly n times the logarithm of n. The second is the walk. Each child and each cookie is looked at once, so the walk takes about n plus m steps, where n is the number of children and m is the number of cookies.

Compare this with a simpler plan that checks every child against every cookie. For 1,000 children and 1,000 cookies, that plan takes about 1,000,000 checks. The sorted walk takes about 2,000 steps after the sort. The sort is the expensive part, and it is still far cheaper than the full comparison.

Common mistakes

These are the mistakes beginners make most often with this method.

Mistake 1: sorting only one list

The method needs both lists sorted. If the cookies are left in their original order, the walk gives the wrong answer. Here is a function with the same loop but no sort on the cookies:

#include <cstddef>
#include <iostream>
#include <vector>
 
std::size_t assignUnsorted(const std::vector<int>& greed, const std::vector<int>& cookies) {
    std::size_t cookie = 0;
    std::size_t happy = 0;
    for (int need : greed) {
        while (cookie < cookies.size() && cookies[cookie] < need) {
            ++cookie;
        }
        if (cookie == cookies.size()) {
            break;
        }
        ++happy;
        ++cookie;
    }
    return happy;
}
 
int main() {
    std::cout << assignUnsorted({1, 2}, {5, 1}) << '\n';
}

With the children {1, 2} and the cookies {5, 1}, the first child takes the 5 because it is the first cookie in the list. The child who needs 2 then finds only a cookie of size 1, which is too small. The output is 1. Sorting the cookies first gives the right answer, which is 2: the child who needs 1 gets the 1, and the child who needs 2 gets the 5.

Mistake 2: comparing a signed index with size()

A common first attempt uses a plain int as the index:

#include <vector>
 
int countBelow(const std::vector<int>& cookies, int limit) {
    int i = 0;
    while (i < cookies.size() && cookies[i] < limit) {
        ++i;
    }
    return i;
}
 
int main() {
    return countBelow({1, 2}, 2);
}

Compiled with -Wall, g++ 15 reports this warning:

signbug.cpp: In function ‘int countBelow(const std::vector<int>&, int)’:
signbug.cpp:5:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    5 |     while (i < cookies.size() && cookies[i] < limit) {
      |            ~~^~~~~~~~~~~~~~~~

The warning means the comparison mixes a signed number (int, which can be negative) with an unsigned number (size(), which cannot). The compiler converts one side to match the other, and the result can be surprising for large or negative values. The fix is to use std::size_t for the index, as the main lesson code does.

Mistake 3: forgetting the end-of-list check

After the while loop, the cookie index may equal cookies.size(). That means there is no cookie left. If the code reads cookies[cookie] at that point, it reads past the end of the vector. C++ does not check this for you when you use []. The program may crash, print a wrong count, or seem to work for a while. This is called undefined behaviour, which means the language does not say what happens.

The check if (cookie == cookies.size()) break; prevents this. cookies.at(cookie) also prevents it, because at throws an exception when the index is out of range. That is safer for learning, but the break version is the usual way to write this loop.

Mistake 4: advancing the cookie index for a child who got nothing

When a child is not fed, the cookie index must not move. The cookie that was too small for this child might still be useful for nobody, but it is not used up. Moving the index past a cookie that was never given away makes the count too small. The code in the main lesson moves cookie forward in two places only. The while loop moves it past cookies that are too small, and the line after the match moves it past the cookie just given away.

Mistake 5: using the wrong comparison

The rule is "a cookie is big enough when its size is at least the need." That means cookies[cookie] >= need. Writing > instead of >= skips a cookie that is exactly the right size. Test with a case where a cookie equals a need, such as the child needing 2 and a cookie of size 2. That case is in Example 2 of the program, where the child needing 2 gets the cookie of size 2.

Practice

Each exercise has its answer below it. Try the exercise on paper or in a file before you read the answer.

1. Trace the walk for children {3, 1, 2} and cookies {1, 1}. Write each step as a line like the trace in worked example 1. What is the answer?

Show the answer

The sorted children are 1, 2, 3. The sorted cookies are 1, 1. Child 1 takes cookie 1, so the count is 1. Child 2 needs 2, the next cookie is 1, which is too small, and no cookies are left. The answer is 1.

2. Write a function totalGiven that takes the children and the cookies and returns the total size of all cookies that were given out. Use assignCookies from the main lesson. For children {1, 2, 3} and cookies {1, 2, 5}, the answer is 8.

Show the answer

long long totalGiven(const std::vector<int>& greed, const std::vector<int>& cookies) {
    auto matches = assignCookies(greed, cookies);
    long long sum = 0;
    for (auto [need, size] : matches) {
        sum += size;
    }
    return sum;
}

The matches are 1 with 1, 2 with 2, and 3 with 5. The sum is 1 + 2 + 5 = 8. The code above returns 8 for this input.

3. The children {2, 1} and the cookies {1, 2} should give an answer of 2. Explain why a loop that walks the children in their original order, without sorting them, can give a smaller answer. Then write down the answer that loop gives.

Show the answer

Without sorting the children, the first child needs 2. The cookies are sorted to 1, 2, so the 1 is skipped and the 2 is given away. The next child needs 1, and no cookies are left, so this child gets nothing. The loop returns 1. Sorting the children puts the need of 1 first, so the 1 is given to the child who needs 1 and the 2 to the child who needs 2. The sorted answer is 2. The loop must sort the children, not only the cookies.

4. Write a function unfedNeeds that returns the needs of the children who did not get a cookie, in sorted order. For children {1, 2, 3, 4} and cookies {2, 2}, the answer is the list 3 4.

Show the answer

std::vector<int> unfedNeeds(const std::vector<int>& greed, const std::vector<int>& cookies) {
    auto matches = assignCookies(greed, cookies);
    std::vector<int> sorted = greed;
    std::sort(sorted.begin(), sorted.end());
 
    std::vector<int> left;
    std::size_t k = 0;
    for (int need : sorted) {
        if (k < matches.size() && matches[k].first == need) {
            ++k;
            continue;
        }
        left.push_back(need);
    }
    return left;
}

The matches are 1 with 2 and 2 with 2. The needs 3 and 4 are not in the matches, so they go into the list. The result is 3 and 4. This works because assignCookies matches children in sorted order, so the matches list and the sorted needs move together.

5. Children {1, 1, 1} and cookies {1, 1, 1, 1} give an answer of 3. Explain why the fourth cookie is not used.

Show the answer

There are only three children, and each child takes at most one cookie. After the three children are fed, the loop has nobody left to give the fourth cookie to. The answer is the number of children that can be fed, which is 3. The number of cookies does not raise the answer above the number of children.

Summary

• Sort both lists, then walk through the children in order of need.
• For each child, skip cookies that are too small and give the first cookie that fits.
• The walk never goes back, so two pointers are enough.
• The method is safe because a cookie too small for the least needy waiting child is too small for every waiting child.
• Use std::size_t for the index and check for the end of the cookie list before reading from it.