Jump game I and II

Why this matters

Many real choices work like a game of hops. You can move up to a certain distance from where you stand, and you want to get to a goal with as few moves as possible, or you want to know whether the goal is reachable at all. Delivery routes, video game levels and network hops all have this shape. Interviewers like this problem because the naive solution tries every combination of hops, and the good solution keeps one number up to date as it reads the list once.

This lesson uses one idea twice. A greedy method makes the choice that looks best right now and never goes back to change it. Here the choice is "remember the farthest place I can reach so far." You need to know for loops, std::vector, std::size_t and std::max from earlier lessons. The graph lessons earlier in the course cover breadth-first search, which is the same level-by-level idea used in part two of this lesson, but you do not need that lesson to follow the code here.

The game

You are given a list of whole numbers called nums. Each number is the most steps you may take from that position. You start at index 0, the first position. An index is the position of an item in a list, counted from zero. Index 0 is the first item, index 1 is the second, and so on.

Take this list.

index:  0  1  2  3  4
nums:  [2, 3, 1, 1, 4]

At index 0 the number is 2, so you may move forward by 1 or by 2 steps. At index 1 the number is 3, so you may move forward by 1, 2 or 3 steps. The last index is 4. The question is whether you can land on index 4.

You can, and one route is 0 -> 1 -> 4. From index 1 you jump 3 steps to reach index 4. You can also go 0 -> 2 -> 3 -> 4, which takes three jumps. The route 0 -> 1 -> 4 uses only two jumps, so two is the fewest jumps for this list.

Two versions of the question come from this game.

• Jump game I: can you reach the last index at all? The answer is true or false.
• Jump game II: you are told the last index can be reached. What is the fewest number of jumps?

The second version also has a common variant where the answer is -1 when the end cannot be reached. This lesson handles that case too.

Part one: track the farthest reach

Start with the simplest question. Do not think about routes yet. Think about a single number called farthest, which means the highest index you can stand on so far.

Here is the rule that keeps farthest correct. Read the list from left to right. At each index i, you can only be there if i is no greater than farthest, because a position beyond farthest has never been reached. If i is reachable, then from i you can reach any index up to i + nums[i]. So you update farthest to the larger of its current value and i + nums[i].

Work through [2, 3, 1, 1, 4] one step at a time.

After index 1, farthest is 4, which is the last index. The answer is already known, so you can stop. Once farthest reaches the last index, the rest of the list does not matter.

Now take [3, 2, 1, 0, 4]. Index 0 gives a reach of 3, so farthest is 3. Indexes 1, 2 and 3 all stay within 3, and their reaches are 3, 3 and 3. Then index 4 appears, but 4 is greater than farthest (3). Nothing before index 4 can jump that far, so the end cannot be reached. The answer is false.

Picture it as a fog that lifts. Each index you can stand on lights up the squares up to its reach. If the fog stops before the last square, there is no path. The farthest variable is the edge of the lit area.

The code

This function returns true or false. It reads the list once, so its running time grows in a straight line with the list length.

#include <algorithm>
#include <cstddef>
#include <vector>
 
bool canReachEnd(const std::vector<int>& nums) {
    std::size_t farthest = 0;
    for (std::size_t i = 0; i < nums.size(); ++i) {
        if (i > farthest) {
            return false;
        }
        farthest = std::max(farthest, i + static_cast<std::size_t>(nums[i]));
        if (farthest >= nums.size() - 1) {
            return true;
        }
    }
    return true;
}

Each line does one job. The if (i > farthest) check catches the case where the fog has stopped. The std::max line widens the lit area. The early return true stops the loop once the last index is lit. The static_cast<std::size_t> turns the int jump length into an unsigned number so it adds cleanly to an index. The jump lengths in this problem are never negative, so the cast does not change a value.

Why the greedy choice is safe

Greedy methods are only useful when you can prove that the choice never hurts. Here is the argument in plain words. The variable farthest only ever holds a position you really can reach, because it is built from positions that were reached. It also never misses a position. If the end can be reached by some route, that route passes only through positions up to farthest at each step, so farthest always covers at least as much as that route. Therefore, if the loop reaches the end of the list without the check i > farthest firing, every position was reachable, and the last one is among them.

You do not need to remember every route. You only need the edge of the lit area.

Part two: count the fewest jumps level by level

Part one tells you whether you can reach the end. Part two asks how many jumps it takes. The idea of levels makes this clear.

Think of the first jump as a set of places you can land on. From index 0 in [2, 3, 1, 1, 4], one jump lands you on index 1 or index 2. Call that set level one. From every place in level one, one more jump gives level two. Each level is the set of places reachable in exactly that many jumps, and each level sits after the one before it. The answer is the first level that contains the last index.

You do not need to store every place in every level. A level is a range of indexes, from the start of the level up to a boundary, and the next level is a range that goes from there to the farthest reach seen inside the current level. So two numbers are enough.

• levelEnd: the last index you can reach using the current number of jumps.
• farthest: the last index you can reach using one more jump.

You read the list once. When your index reaches levelEnd, you have used up all the places in the current level. That means you must jump one more time, so you add one to the jump count and move levelEnd out to farthest.

Here is the trace for [2, 3, 1, 1, 4]. The last index is 4.

At index 2, levelEnd has reached 4, which is the last index. The answer is 2.

Notice what the second jump did. It did not go from index 0 to index 2 and then to 4 on purpose. The method only tracked the boundary. The number 4 came from index 1, which is in level one, and index 1 reaches 4. That is why the answer is two and not three.

The code

This version returns -1 when the end cannot be reached. That case is part of the common variant of the problem, and it costs only one extra check.

#include <algorithm>
#include <cstddef>
#include <vector>
 
int minJumps(const std::vector<int>& nums) {
    const std::size_t last = nums.size() - 1;
    if (last == 0) {
        return 0;
    }
    int jumps = 0;
    std::size_t levelEnd = 0;
    std::size_t farthest = 0;
    for (std::size_t i = 0; i < last; ++i) {
        farthest = std::max(farthest, i + static_cast<std::size_t>(nums[i]));
        if (i == levelEnd) {
            if (farthest == i) {
                return -1;
            }
            ++jumps;
            levelEnd = farthest;
            if (levelEnd >= last) {
                return jumps;
            }
        }
    }
    return -1;
}

The loop stops at i < last, not at the end of the list. There is no need to read the last index as a starting point, because you only need to reach it, not leave it. The check farthest == i at a level boundary means nothing beyond i can be reached, so the end is unreachable. In that case the function returns -1.

A second example

Take [2, 0, 0]. The first jump from index 0 can reach index 2, which is the last index. So one jump is enough.

levelEnd is now 2, which is at least last (2). The function returns 1.

A third example with a dead end

Take [3, 2, 1, 0, 4]. Part one said the end is unreachable. Part two should say -1.

Index 0 has reach 3, so the first level ends at 3, and jumps becomes 1. Indexes 1, 2 and 3 all have reaches of at most 3, so farthest stays at 3. At index 3, the value levelEnd is also 3, so the loop checks whether farthest equals i. Both are 3, so no jump can leave the current position. The function returns -1.

The check matters. Without it, the loop would try to jump again from the same place, and levelEnd would never grow. The loop would then end and return -1 anyway, but the variable jumps would count a jump that cannot be made. Keep the check.

Running the code

The program below runs both functions on a set of lists and prints the results. Save it as jump.cpp and build it with the command below.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
 
bool canReachEnd(const std::vector<int>& nums) {
    std::size_t farthest = 0;
    for (std::size_t i = 0; i < nums.size(); ++i) {
        if (i > farthest) {
            return false;
        }
        farthest = std::max(farthest, i + static_cast<std::size_t>(nums[i]));
        if (farthest >= nums.size() - 1) {
            return true;
        }
    }
    return true;
}
 
int minJumps(const std::vector<int>& nums) {
    const std::size_t last = nums.size() - 1;
    if (last == 0) {
        return 0;
    }
    int jumps = 0;
    std::size_t levelEnd = 0;
    std::size_t farthest = 0;
    for (std::size_t i = 0; i < last; ++i) {
        farthest = std::max(farthest, i + static_cast<std::size_t>(nums[i]));
        if (i == levelEnd) {
            if (farthest == i) {
                return -1;
            }
            ++jumps;
            levelEnd = farthest;
            if (levelEnd >= last) {
                return jumps;
            }
        }
    }
    return -1;
}
 
int main() {
    std::vector<std::vector<int>> examples = {
        {2, 3, 1, 1, 4},
        {3, 2, 1, 0, 4},
        {2, 3, 0, 1, 4},
        {2, 0, 0},
        {0},
    };
    for (const auto& nums : examples) {
        std::cout << std::boolalpha << "can reach end: " << canReachEnd(nums)
                  << ", fewest jumps: " << minJumps(nums) << '\n';
    }
}

Build and run it with these commands.

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

The output is as follows.

can reach end: true, fewest jumps: 2
can reach end: false, fewest jumps: -1
can reach end: true, fewest jumps: 2
can reach end: true, fewest jumps: 1
can reach end: true, fewest jumps: 0

The first line matches the walkthrough above. The {0} list has only one index, which is already the last index, so zero jumps are needed. The build prints no warnings.

Common mistakes

Forgetting the gap check

Part one needs the check if (i > farthest) before it reads the value at i. Without it, the function says a list is reachable when it is not. This version has the check removed.

bool noGapCheck(const std::vector<int>& nums) {
    std::size_t farthest = 0;
    for (std::size_t i = 0; i < nums.size(); ++i) {
        farthest = std::max(farthest, i + static_cast<std::size_t>(nums[i]));
    }
    return farthest >= nums.size() - 1;
}

Given {0, 2}, the function returns true. Index 0 has a jump length of 0, so it cannot move, and index 1 can never be reached. The real output is:

true

The correct answer is false. The fix is the if (i > farthest) check from part one.

Using the jump length as the destination

A common first idea is to jump directly to index nums[i]. That is wrong. The number at index i is the maximum distance, not the exact landing place. Index 1 in [2, 3, 1, 1, 4] holds 3, which means you may jump up to three steps forward from index 1, landing on index 2, 3 or 4. Treating 3 as "land on index 3" gives the wrong reach and therefore the wrong answer.

Counting a jump at the wrong time

In part two, a jump is counted when i reaches levelEnd, not when i moves forward. If you add one to jumps on every step, the count grows with the length of the list, not with the number of jumps. Count only at the boundary.

Forgetting the empty list

minJumps computes nums.size() - 1. For an empty list, nums.size() is 0, and 0 - 1 on an unsigned type wraps around to a very large number. The problem statement always gives at least one index, so minJumps assumes that. If your input can be empty, check nums.empty() first and return an answer before the subtraction.

A compiler warning about signed and unsigned numbers

Comparing an int loop counter with size() gives a warning. Here is a version with that mistake.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3};
    for (int i = 0; i < nums.size(); ++i) {
        std::cout << nums[i] << '\n';
    }
}

Building it with g++ -std=c++20 -Wall -o sign sign.cpp prints this warning.

sign.cpp: In function ‘int main()’:
sign.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < nums.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

The fix is to use std::size_t for the counter, as the functions in this lesson do.

Practice

Exercise 1. Trace canReachEnd on [1, 0, 1, 0]. Write the value of farthest after each index you read, and say whether the answer is true or false.

Show the answer

Index 0 has reach 1, so farthest is 1. Index 1 has reach 1, so farthest stays 1. At index 2, the check i > farthest is 2 > 1, which is true, so the function returns false. Index 2 cannot be reached.

Exercise 2. Find the fewest jumps for [1, 1, 1, 1] using minJumps. Trace the values of levelEnd and jumps.

Show the answer

Index 0 has reach 1, so levelEnd becomes 1 and jumps becomes 1. Index 1 has reach 2, and farthest becomes 2. Index 1 equals levelEnd, so jumps becomes 2 and levelEnd becomes 2. Index 2 has reach 3, farthest becomes 3. Index 2 equals levelEnd, so jumps becomes 3 and levelEnd becomes 3, which equals the last index. The answer is 3.

Exercise 3. Explain why the loop in minJumps stops at i < last and not at i < nums.size(). What would change if the loop read the last index too?

Show the answer

The last index is the goal, so the loop never needs to take a jump from it. The function returns as soon as levelEnd reaches last, so the loop never gets to the last index as a starting point in a successful run. The bound i < last states that intent directly. Changing it to i < nums.size() would not change any answer in this version, but a reader would have to work out why.

Exercise 4. Write a version of canReachEnd that returns the index of the first position that cannot be reached, or -1 if every position can be reached. Use the same loop.

Show the answer

int firstUnreachable(const std::vector<int>& nums) {
    std::size_t farthest = 0;
    for (std::size_t i = 0; i < nums.size(); ++i) {
        if (i > farthest) {
            return static_cast<int>(i);
        }
        farthest = std::max(farthest, i + static_cast<std::size_t>(nums[i]));
    }
    return -1;
}

For [1, 0, 1, 0], the function returns 2, because index 2 is the first position the fog does not reach.

Exercise 5. Explain in your own words why the greedy choice of always keeping the farthest reach is safe for Jump game I. Use the phrase "lit area" in your explanation.

Show the answer

The lit area is every index that can be reached so far. The value farthest is its right edge. Every index inside the lit area is reachable, because each one was lit by an index before it. Taking the largest reach at each step never removes an index from the lit area, so it can only make the lit area grow. If some route reaches the last index, every index on that route is inside the lit area when it is needed, so the loop does not stop early.

Summary

• Jump game I asks whether the last index is reachable. Track farthest, the highest index you can stand on so far, and stop with false when the loop reaches an index beyond it.
• Jump game II asks for the fewest jumps. Track levelEnd and farthest, and add one jump each time the loop reaches levelEnd.
• Each function reads the list once, so the running time grows in a straight line with the list length.
• If farthest does not move past the current index at a level boundary, the end cannot be reached, and -1 is the answer.
• The number at each index is the largest jump allowed, not the exact landing place.
• The gas station lesson in this module uses another greedy idea, a running balance, on a circle of stations.