Candy distribution with two passes

Why this matters

Some problems cannot be solved by looking at a list once. A rule that depends on both neighbours of an item can be broken by a change made later in the scan. The usual fix is to look twice: once in each direction. This lesson teaches that pattern with a problem about giving out candy in a line.

The method still uses the greedy idea from the previous lesson, where each step makes the best local choice. Here the choice at each child is only made from one side at a time. The second pass then fixes what the first pass could not see.

You need std::vector and for loops. You also need to be comfortable reading an index such as ratings[i - 1], which means "the value just before position i". The previous lesson in this module, on assigning cookies, uses a similar walk, but it only goes forward through the lists once.

The problem in plain words

Imagine a row of children standing in a line. Each child has a rating, which is a number a teacher gave for their work. Each child must get candy from a teacher. The teacher follows two rules.

• Every child gets at least one candy.
• A child with a higher rating than a neighbour gets more candy than that neighbour.

The rule only applies between direct neighbours. Two children far apart have no rule between them. The goal is to use the fewest candies in total while following both rules.

Here is a small case. The ratings are 1 0 2, which means the first child has rating 1, the second has rating 0, and the third has rating 2.

• The middle child has the lowest rating. Both neighbours have higher ratings, so the middle child must get fewer candies than each of them. One candy is the lowest possible, so the middle child gets 1.
• The first child has rating 1, which is higher than the middle child's rating of 0. So the first child must get more than 1. The smallest choice is 2.
• The third child has rating 2, which is higher than 0. The same reasoning gives 2.

The answer is 2 1 2, which adds up to 5. This is the example the program in the next sections checks first.

Two terms are used in this lesson:

• A neighbour is the child directly to the left or right. The first child has only a right neighbour, and the last child has only a left neighbour.
• A pass is one full walk through the list, from one end to the other.

Why one pass is not enough

A natural first idea is to walk left to right. Give each child one candy if their rating is not higher than the child on the left. If their rating is higher, give them one more candy than the child on the left. This handles the rule against the left neighbour, and that is all it handles.

Try it on the ratings 3 2 1. The left-to-right walk gives every child 1 candy, because no child has a higher rating than the child on the left. The first child has rating 3, which is higher than the second child's rating of 2. The rule says the first child must get more candy, but both have 1. The rule is broken. A walk in one direction cannot see the child on the right.

The walk from right to left has the same problem in mirror image. It handles the right neighbour and ignores the left.

So the fix is to do both walks and combine the results. The left walk produces a list of candies that satisfies the left-neighbour rule. The right walk produces a list that satisfies the right-neighbour rule. Each child needs enough candy to satisfy both. The safe choice is the larger of the two values at each child.

The two-pass idea

The method has three parts.

1. Start every child with 1 candy.
2. Pass 1, left to right: if a child's rating is higher than the child on the left, give this child one more candy than the left child has.
3. Pass 2, right to left: if a child's rating is higher than the child on the right, give this child one more candy than the right child has. If this child already has more candy than that, keep the larger value.

The second pass never lowers a value. It only raises some values. It uses std::max to keep the bigger number. That is the key detail. If the second pass simply wrote the new value, it could take away candy that the first pass gave to satisfy the left rule.

Why does keeping the larger value work? The first pass gives each child at least what the left rule needs. The second pass gives each child at least what the right rule needs. Taking the larger number at each child keeps both promises. Neither rule asks for more than the larger value, so the total is not bigger than it needs to be.

A brute-force check is a stronger test than this argument. A brute-force check tries every possible set of candy counts for a small input and keeps the cheapest set that follows both rules. The two-pass method was checked this way on every short input with ratings 0, 1 or 2 and lengths 1 to 6. That is 1,092 inputs in total. The two-pass method matched the smallest valid total in every one of them.

Worked example 1: the first case

Take the ratings 1 0 2. Start with 1 1 1.

Pass 1, left to right:

Child 2 (rating 0) is not higher than child 1 (rating 1). Stays at 1.
Child 3 (rating 2) is higher than child 2 (rating 0). Gets 1 + 1 = 2.
Result after pass 1: 1 1 2

Pass 2, right to left:

Child 2 (rating 0) is not higher than child 3 (rating 2). No change.
Child 1 (rating 1) is higher than child 2 (rating 0), so child 1 must get more than child 2.
  Child 1 gets max(1, 1 + 1) = 2.
Result after pass 2: 2 1 2

The total is 5. The program below prints the same result.

Look at the second pass again. It starts at the right end. It checks each pair of neighbours from right to left. When the left child is higher than the right child, the left child must get more candy. In this case the left child is the first child, with rating 1, and the right child is the middle child, with rating 0. So the first child moves from 1 candy to 2.

Writing the code in C++

The code below does both passes. The function candyCounts returns the candy count for each child. The function minCandies adds them up. The function isValid checks that the answer follows both rules, so the output can be checked by the program itself.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
 
// Each child gets at least 1 candy. A child with a higher rating than a
// neighbour gets more candy than that neighbour.
std::vector<int> candyCounts(const std::vector<int>& ratings) {
    const std::size_t n = ratings.size();
    std::vector<int> candy(n, 1);
    if (n == 0) {
        return candy;
    }
 
    // Pass 1, left to right: fix the rule against the left neighbour.
    for (std::size_t i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1]) {
            candy[i] = candy[i - 1] + 1;
        }
    }
 
    // Pass 2, right to left: fix the rule against the right neighbour.
    // Keep the larger value so the left rule still holds.
    for (std::size_t i = n - 1; i > 0; --i) {
        if (ratings[i - 1] > ratings[i]) {
            candy[i - 1] = std::max(candy[i - 1], candy[i] + 1);
        }
    }
    return candy;
}
 
long long minCandies(const std::vector<int>& ratings) {
    auto candy = candyCounts(ratings);
    return std::accumulate(candy.begin(), candy.end(), 0LL);
}
 
// Returns true when both rules hold for every neighbour pair.
bool isValid(const std::vector<int>& ratings, const std::vector<int>& candy) {
    for (std::size_t i = 0; i < ratings.size(); ++i) {
        if (candy[i] < 1) return false;
        if (i > 0 && ratings[i] > ratings[i - 1] && candy[i] <= candy[i - 1]) return false;
        if (i > 0 && ratings[i] < ratings[i - 1] && candy[i] >= candy[i - 1]) return false;
    }
    return true;
}
 
void show(const std::vector<int>& ratings) {
    auto candy = candyCounts(ratings);
    std::cout << "ratings:";
    for (int r : ratings) std::cout << ' ' << r;
    std::cout << "\n  candies:";
    for (int c : candy) std::cout << ' ' << c;
    std::cout << "\n  total: " << minCandies(ratings)
              << ", valid: " << std::boolalpha << isValid(ratings, candy) << '\n';
}
 
int main() {
    show({1, 0, 2});
    show({1, 2, 2});
    show({1, 3, 4, 5, 2});
    show({1, 2, 3, 0});
    show({1, 2, 87, 87, 87, 2, 1});
    show({5});
    show({});
}

Compile and run it with the same flags used in the previous lesson:

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

The output is:

ratings: 1 0 2
  candies: 2 1 2
  total: 5, valid: true
ratings: 1 2 2
  candies: 1 2 1
  total: 4, valid: true
ratings: 1 3 4 5 2
  candies: 1 2 3 4 1
  total: 11, valid: true
ratings: 1 2 3 0
  candies: 1 2 3 1
  total: 7, valid: true
ratings: 1 2 87 87 87 2 1
  candies: 1 2 3 1 3 2 1
  total: 13, valid: true
ratings: 5
  candies: 1
  total: 1, valid: true
ratings:
  candies:
  total: 0, valid: true

A few details in the code are worth knowing.

The guard if (n == 0) returns early. Without it, n - 1 would be a very large number, because std::size_t cannot go below zero. The second loop would then read far outside the vector. The mistakes section shows this.

The second loop uses i > 0 as its stop condition, not i >= 0. The index is unsigned, so i >= 0 is always true. A loop that counts down past zero never stops.

std::max(candy[i - 1], candy[i] + 1) needs both values to have the same type. Both are int, so the call compiles without any cast.

Worked example 2: equal neighbours

Equal ratings give no rule between two children. Take the ratings 1 2 2. The third child and the second child have the same rating, so neither must get more than the other.

Pass 1 gives 1 2 1. The second child is higher than the first, so it gets 2. The third child has the same rating as the second, so it gets 1 again.

Pass 2 finds no pair where the left child is higher than the right child. The result stays 1 2 1, and the total is 4. The program prints the same answer.

Equal ratings are a common source of confusion. The rule says "higher rating", not "same or higher". Two children with the same rating can have different candy counts or the same count.

Worked example 3: a second pass that changes something

Take the ratings 1 3 4 5 2. The left walk gives 1 2 3 4 1. The right walk checks the end of the line.

Start the right walk at the last child, who has rating 2. The child before them has rating 5, which is higher. So the child with rating 5 must have more candy than the child with rating 2, who has 1 candy. That means at least 2. The child with rating 5 already has 4 candies, so std::max keeps 4. Nothing changes.

The rest of the right walk changes nothing either. The result is 1 2 3 4 1, which totals 11, and the program prints that same answer.

This example shows that the second pass often changes nothing. That is fine. It only has to make a change when the first pass left a rule broken. The program still checks every pair, which is why it is written as a full loop and not as a special case.

Worked example 4: a longer line

Take the ratings 1 2 87 87 87 2 1. The middle three children have the same rating, 87, which is the highest in the line. They do not need to be compared with each other.

Pass 1 from the left gives 1 2 3 1 1 1 1. The child with rating 2 at position 1 gets 2 because the child before has rating 1. The child with rating 87 at position 2 gets 3 because it is higher than the child before. The child at position 3 has the same rating as the child before, so it gets 1. The ratings fall at the right end, and those children also get 1 each.

Pass 2 from the right fixes the falling side. The child at position 5 has rating 2, which is higher than the child at position 6 with rating 1. So position 5 must have more than position 6. Position 5 gets max(1, 1 + 1), which is 2. Then position 4 has rating 87, which is higher than position 5 with rating 2. So position 4 must have more than position 5. It gets max(1, 2 + 1), which is 3.

The final result is 1 2 3 1 3 2 1, with a total of 13. The program prints the same total.

Checking an answer by hand

To check a candy answer on paper, go through each pair of neighbours and ask which child should have more. Then compare the candy counts for that pair.

Take the ratings 1 3 4 5 2 with the answer 1 2 3 4 1. There are four neighbour pairs.

• Ratings 1 and 3: the second child is higher, and 2 is more than 1. Correct.
• Ratings 3 and 4: the third child is higher, and 3 is more than 2. Correct.
• Ratings 4 and 5: the fourth child is higher, and 4 is more than 3. Correct.
• Ratings 5 and 2: the fourth child is higher, and 4 is more than 1. Correct.

Every child also has at least one candy. The total is 11. The isValid function in the program runs this same check on every pair, and it returns true for this answer.

Common mistakes

These are the mistakes beginners make with this method.

Mistake 1: only one pass

If only the left-to-right pass runs, the rule against the right neighbour is never checked. Here is a program with only the first pass:

#include <cstddef>
#include <iostream>
#include <vector>
 
std::vector<int> leftOnly(const std::vector<int>& ratings) {
    const std::size_t n = ratings.size();
    std::vector<int> candy(n, 1);
    for (std::size_t i = 1; i < n; ++i)
        if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
    return candy;
}

For the ratings 3 2 1, the output is 1 1 1. The first child has a higher rating than the second, but both have 1 candy. The check isValid marks this as false. The fix is the second pass.

Mistake 2: overwriting instead of taking the larger value

The second pass must keep the bigger number. Writing candy[i - 1] = candy[i] + 1 looks similar, but it can lower a value that the first pass set. Here is that version, with the same validity check as the main program:

#include <cstddef>
#include <iostream>
#include <vector>
 
bool isValid(const std::vector<int>& ratings, const std::vector<int>& candy) {
    for (std::size_t i = 0; i < ratings.size(); ++i) {
        if (candy[i] < 1) return false;
        if (i > 0 && ratings[i] > ratings[i - 1] && candy[i] <= candy[i - 1]) return false;
        if (i > 0 && ratings[i] < ratings[i - 1] && candy[i] >= candy[i - 1]) return false;
    }
    return true;
}
 
std::vector<int> overwriteVersion(const std::vector<int>& ratings) {
    const std::size_t n = ratings.size();
    std::vector<int> candy(n, 1);
    for (std::size_t i = 1; i < n; ++i)
        if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
    for (std::size_t i = n - 1; i > 0; --i)
        if (ratings[i - 1] > ratings[i]) candy[i - 1] = candy[i] + 1;
    return candy;
}
 
void print(const std::vector<int>& ratings, const std::vector<int>& c) {
    for (int x : c) std::cout << ' ' << x;
    std::cout << ", valid: " << std::boolalpha << isValid(ratings, c) << '\n';
}
 
int main() {
    print({1, 2, 3, 0}, overwriteVersion({1, 2, 3, 0}));
}

The output for the ratings 1 2 3 0 is 1 2 2 1, valid: false. The first pass gave the third child 3 candies. The second pass then set the third child to 2, which is the same as the second child's 2. The third child has a higher rating than the second, so it needs more. The check catches the mistake, but the program does not fix it.

Mistake 3: the loop that counts down past zero

Because the index is std::size_t, it cannot be negative. A loop written as for (std::size_t i = n - 1; i >= 0; --i) never stops, since i >= 0 is always true. When i reaches 0 and decreases, it wraps around to a very large number. The program then reads far outside the vector. C++ does not check this when you use [], so the result is undefined behaviour. The program may crash or print wrong numbers.

The fix is the condition i > 0 used in the main code. The loop then reads ratings[i - 1] only when i is at least 1.

Mistake 4: no guard for an empty list

If the ratings list is empty, n - 1 wraps around to a very large number. The second loop then starts far past the end of the list. The guard if (n == 0) return candy; in candyCounts prevents this. The empty case returns an empty result, and the total is 0.

Mistake 5: using >= where the rule says >

The rule compares ratings with > and gives more candy only when the rating is higher. Writing >= makes equal neighbours get extra candy they do not need. The total then becomes larger than the minimum. Take the ratings 1 2 2 and a first pass that uses >=. The third child would get 3 candies, because its rating equals the second child's and the rule is applied anyway. The total would be 6 instead of 4.

Practice

Each exercise has its answer below it. Work on paper or in a file first.

1. Find the candy counts for the ratings 1 2 3 2 1. Use both passes. Write the result after pass 1 and after pass 2, then give the total.

Show the answer

After pass 1 the counts are 1 2 3 1 1. In pass 2, position 3 has rating 2, which is higher than position 4's rating of 1, so position 3 rises from 1 to 2. Position 2 has rating 3, which is higher than position 3's rating of 2, and it already has 3 candies, so it stays. The final counts are 1 2 3 2 1 with a total of 9.

2. Find the minimum total for the ratings 4 4 4. Explain why no child needs more than one candy.

Show the answer

All three ratings are equal. No pair of neighbours has different ratings, so no rule applies. Each child needs only the minimum of one candy. The counts are 1 1 1 and the total is 3.

3. Ratings that fall from left to right, such as 5 4 3 2 1, are a case where the first pass does nothing and the second pass does all the work. Predict the counts and the total for 5 4 3 2 1. Then check your answer with the program.

Show the answer

The first pass gives every child 1 candy, because no child is higher than the child on the left. The second pass works from the right. The last child gets 1. Each child before it has a higher rating, so it gets one more than the child after it. The counts are 5 4 3 2 1, and the total is 15.

4. The ratings 1 3 2 are given the candy counts 1 2 1. Is this a valid answer? Explain using the two rules.

Show the answer

Yes. The second child has rating 3, which is higher than the first child's rating of 1. The second child has 2 candies, which is more than the first child's 1. The third child has rating 2, which is lower than the second child's rating of 3. The third child has 1 candy, which is less than the second child's 2. Every child has at least one candy. The isValid function returns true for this answer.

5. Write a function candyTotalSquared that takes the ratings and returns the sum of the squares of each child's candy count. Use candyCounts from the main lesson. Give the result for the ratings 1 0 2.

Show the answer

long long candyTotalSquared(const std::vector<int>& ratings) {
    auto candy = candyCounts(ratings);
    long long sum = 0;
    for (int c : candy) {
        sum += static_cast<long long>(c) * c;
    }
    return sum;
}

For the ratings 1 0 2, the counts are 2, 1 and 2. The squares are 4, 1 and 4. The sum is 9. The cast to long long is there so the multiplication does not overflow for large counts.

Summary

• Give every child one candy, then walk the line left to right to satisfy the rule against the left neighbour.
• Walk the line right to left to satisfy the rule against the right neighbour, and keep the larger value at each child.
• Taking the larger value is what keeps the first pass's work from being undone.
• Guard the empty case and use i > 0 as the loop condition, because the index is unsigned.
• Use > for the rating comparison, since equal ratings carry no rule.