Jump game I and II in Python

Why this matters

Many programs move through a row of cells, where each cell tells you how far you may move from it. A game character on a path of platforms, a music playlist that skips ahead by a set number of songs, and a packet that hops between routers all fit this shape. Two questions come up again and again. Can you reach the end at all? If so, what is the fewest number of moves?

This lesson answers both questions with greedy methods. Jump game I asks only whether the end is reachable. Jump game II asks for the fewest jumps. Both problems use one list and one loop, and both need a short argument to show that the loop is correct. Gas station, the next lesson in this module, uses a similar running-total idea on a circle.

By the end of this lesson you will be able to read the list rule, track the farthest reach in Python, count jumps in levels, and check your code with a small brute-force program.

The problem in plain words

You are given a list of whole numbers called nums. A list stores values in order, and each value is reached by its position, called an index. Indexes start at 0. The first value is at index 0, and the last value is at index len(nums) - 1. The function len returns how many items a list has.

The number at each index is the maximum jump length from that index. A jump of length k moves you forward by any amount from 1 to k. If nums[2] is 3, you may move from index 2 to index 3, index 4, or index 5. You may move less than the maximum. A value of 0 means you cannot move forward from that index at all.

You start at index 0. You want to reach the last index. In jump game I, the question is yes or no. In jump game II, the question is how many jumps you need at least. The problem guarantees that the last index can be reached in jump game II, so you never have to report "impossible" there.

Take this list:

index:  0  1  2  3  4
nums:   2  3  1  1  4

From index 0 you can jump to index 1 or index 2. From index 1 you can reach indexes 2, 3 and 4. So the last index is reachable. The fewest jumps is 2: from 0 to 1, then from 1 to 4.

A jump from index 1 with length 3 lands on index 4, which is the last index, so the path 0 -> 1 -> 4 uses 2 jumps. Index 2 holds 1, so it can reach only index 3. That makes 0 -> 1 -> 4 the only 2-jump path.

Jump game I: track the farthest reach

The idea

Suppose you are standing somewhere and you ask one question: what is the farthest index I could possibly stand on? Call that number farthest. Start with farthest = 0, since you start at index 0.

Now walk through the list from left to right. At index i, you can get there only if i is at most farthest. If i is past farthest, nothing before it could have reached it, so the end is unreachable. If i is reachable, then from i you can reach index i + nums[i]. Update farthest to the larger of the old value and i + nums[i].

The greedy choice here is not a single move. It is the decision to keep only the farthest reach, and not to remember every possible spot you could stand on. That is safe, because a larger farthest never makes the answer worse.

A small example by hand

Use nums = [3, 2, 1, 0, 4]. Read it as a table:

i     0  1  2  3  4
nums  3  2  1  0  4

Start with farthest = 0.

• At i = 0: index 0 is reachable because 0 <= farthest. The jump reaches 0 + 3 = 3. Set farthest = 3. The last index is 4, so keep going.
• At i = 1: 1 <= 3, so index 1 is reachable. The jump reaches 1 + 2 = 3. farthest stays 3.
• At i = 2: 2 <= 3. The jump reaches 2 + 1 = 3. farthest stays 3.
• At i = 3: 3 <= 3. The jump reaches 3 + 0 = 3. farthest stays 3. Index 3 cannot move forward.
• At i = 4: 4 > 3. Index 4 is not reachable, so the answer is no.

The answer for this list is False. Every route from index 0 stops at index 3 or earlier. The last index is 4, and no route touches it.

The Python code

A function defined at the top level of a file can be called from anywhere below its definition. The max function is built in, so no import is needed.

The variable last holds the index of the final cell. range(last + 1) produces the numbers 0, 1, up to last, which are the indexes of the list. The if farthest >= last check returns early, which stops the loop as soon as the answer is known. When the loop reaches last, the early check always fires, so the final return True never runs. Python needs a value to return on every path, so the line stays.

The f-string f"canReach={can_reach_end(nums)}" puts the result of the call into the text. Python prints True and False with a capital letter. This is different from Java, which prints true and false.

Here is the output for several lists:

[2, 3, 1, 1, 4] canReach=True
[3, 2, 1, 0, 4] canReach=False
[0] canReach=True
[1, 0, 1, 0] canReach=False
[2, 0, 0] canReach=True
[1, 1, 1, 1] canReach=True

The list [0] has only one index, and you are already on it, so the answer is True. The list [1, 0, 1, 0] fails at index 2, because index 1 holds 0 and nothing before index 2 can reach it.

Why the loop is safe

The loop depends on one fact: the reachable indexes form an unbroken block that starts at 0. A jump of length k from a reachable index i lands on every index from i + 1 to i + k. There are no gaps, because a jump never skips an index on the way. So the reachable set is always 0, 1, 2, ..., farthest, with no holes.

If that is true, then checking whether i is at most farthest is the same as checking whether i is reachable. The loop stops with False the first time it finds an index beyond the block. It returns True once the block covers the last index. Nothing is missed.

The loop also runs in one pass. With n cells it does about n steps, and it uses only a few integers of extra memory.

Jump game II: count jumps level by level

Levels as a picture

Jump game II asks for the fewest jumps. A simple way to see the problem is to draw levels. Level 0 is the start, which holds only index 0. Level 1 holds every index you can reach with one jump. Level 2 holds every index you can reach with two jumps, and so on.

Using the list [2, 3, 1, 1, 4]:

level 0:  index 0
level 1:  indexes 1 to 2     (reached from 0, which has value 2)
level 2:  indexes 3 to 4     (reached from 1 or 2)

The last index is 4, and it first appears in level 2. So the answer is 2.

Two facts make this work. First, each level is an unbroken block of indexes, the same as in jump game I. Second, the block for the next level ends at the farthest index reachable from any index in the current level. The end of level 1 is index 2. The farthest reach from indexes 0, 1 and 2 is max(0+2, 1+3, 2+1) = 4. So level 2 ends at index 4.

The Python code

Keep two numbers while you sweep the list. cur_end is the last index of the current level. farthest is the farthest index reachable from the indexes seen so far. When the sweep reaches cur_end, you have finished the current level, so you count one more jump and move cur_end to farthest.

The loop goes up to last - 1, not last. The range(last) call produces the numbers 0 up to last - 1. The last index is the destination. We never need to jump from it, so it is not included in the sweep. This is the most common source of an off-by-one error (a loop that runs one step too many or too few) in this problem, and the mistakes section shows what goes wrong.

Trace the example [2, 3, 1, 1, 4]:

• i = 0: farthest = max(0, 0 + 2) = 2. Since i == cur_end (both are 0), count one jump: jumps = 1, cur_end = 2.
• i = 1: farthest = max(2, 1 + 3) = 4. i is not cur_end, so nothing else happens.
• i = 2: farthest = max(4, 2 + 1) = 4. Now i == cur_end, so jumps = 2, cur_end = 4. Since 4 >= last, stop.

The function returns 2.

Here is the program output for the reachable lists:

[2, 3, 1, 1, 4] minJumps=2
[0] minJumps=0
[2, 0, 0] minJumps=1
[1, 1, 1, 1] minJumps=3
[5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0] minJumps=3

The list [0] needs 0 jumps, because you already stand on the last index. The function works because the loop never runs when last is 0.

Why the level count is the fewest

Let E_k be the largest index you can reach with at most k jumps. The indexes reachable with at most k jumps form the block from 0 to E_k. This is the same unbroken-block fact from jump game I.

The key step is this: E_(k+1) is the largest of i + nums[i] over all i from 0 to E_k. Any index reachable with k + 1 jumps comes from some index that is reachable with k jumps, and the best landing spot from that index is i + nums[i]. So the next level depends only on the single biggest reach, not on which exact spot you chose inside the current level.

The function finds the smallest k with E_k >= last. That k is the fewest jumps, by definition. The sweep computes E_1, E_2, and so on in order, because cur_end takes the value of farthest at the moment the level ends.

Why the greedy choice is safe

Inside one level, you do not need to know which index you actually land on. You only need the largest reach that the level can give. Choosing the jump that goes farthest is therefore safe: any other choice gives a smaller farthest, and a smaller reach can never help you finish in fewer jumps.

Compare this with a naive rule: from where you stand, jump to the reachable index with the largest value. That rule looks sensible, but it can fail. Take nums = [4, 2, 0, 0, 1, 0]. From index 0 you can reach indexes 1 to 4. Index 1 holds the largest value, 2, so the naive rule jumps there. From index 1 you can only reach indexes 2 and 3, and both hold 0, so the naive rule is stuck. Index 4 holds 1, which is smaller, but index 4 reaches the last index in one more jump. The fewest jumps is 2, and the level method finds it by tracking reach, not value.

A harder example

Take nums = [5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0]. The last index is 11. Here is the sweep, step by step:

• Level 0 is index 0. Its reach is 0 + 5 = 5. So cur_end becomes 5 after one jump.
• Level 1 covers indexes 1 to 5. The farthest reach among them is 1 + 9 = 10 (from index 1). So cur_end becomes 10 after the second jump.
• Level 2 covers indexes 6 to 10. The farthest reach is 8 + 3 = 11 (from index 8). That is at least the last index, so the third jump finishes.

The answer is 3. A brute-force check agrees, and the random tests described below cover many cases like this one.

The breadth-first search (BFS, described below) in the test program is a plain way to check the answer. It visits indexes level by level, which is the same idea as the greedy sweep, but it stores every index in a queue, explained below. The greedy method needs no queue. It runs in one pass with a few integers, which is faster and uses less memory.

Checking the code with a brute-force search

A brute-force check uses a simple method that is slow but easy to trust, then compares the results. For jump game II, the brute-force method is a breadth-first search: it starts at index 0, looks at every index it can jump to, and records how many jumps each index needs. The first time it visits the last index, it has the answer.

The Python version uses a deque, which is a double-ended queue from the collections module. A queue is a line where items join at one end and leave from the other. The popleft method removes the first item from the line in constant time.

The dist dictionary records the number of jumps for each index the search has reached. The j not in dist check stops the search from visiting an index twice. The function returns -1 when the search runs out of indexes, which means the last index cannot be reached.

The program generates 200,000 random lists. Each list has between 1 and 12 cells, and each cell holds a value from 0 to 4. The random.seed(2026) line makes the random numbers the same on every run. The assert lines stop the program with an error if the two methods disagree. The output is:

random cases checked: 200000
reachable cases: 140092

The reachable count comes from Python 3.14. The random module can produce different numbers on another Python version, so that count may differ. The program prints no error, which means the reachability check and the fewest-jump count agreed on every list.

A random test does not prove the code is correct. It does show that the reasoning and the code agree on many cases, including the awkward ones with zeros in the middle. When you write a greedy method, a random test like this is a cheap way to find a mistake you did not think of.

Common mistakes

Counting the last arrival as an extra jump

A common version of the loop runs up to the last index, not one step short of it. Here is that version:

It prints:

off-by-one jumps: 3

The correct answer is 2. At i = 4, the index is cur_end, so the loop counts a jump from the last index. You have already arrived, so that jump does not exist. Stop the loop at last - 1, or check cur_end >= last before counting.

Using the wrong test in jump game I

Jump game I must return False when i > farthest. A version that tests i >= farthest is wrong. farthest starts at 0, so the test is true at index 0 for every list, and the function returns False at once. On [2, 0, 1] the correct answer is True, because index 0 can jump to index 2. Use i > farthest.

Running jump game II on an unreachable list

Jump game II assumes the last index can be reached. If you give it a list that cannot be reached, the function still returns a number, and that number has no meaning. On [1, 0, 1, 0] it returns 2, but the correct answer is "impossible". If the problem does not guarantee reachability, run jump game I first, or check farthest >= last after the loop.

A typo in an attribute name

Python checks a name when the line that uses it runs. A misspelled name is found only when that line is reached, and no earlier check catches it. A list has no attribute called lenght. The length of a list comes from the built-in function len(nums). This program shows the error:

nums = [2, 3, 1, 1, 4]
print(nums.lenght)

The output is:

Traceback (most recent call last):
  File "<your file path>", line 2, in <module>
    print(nums.lenght)
          ^^^^^^^^^^^
AttributeError: 'list' object has no attribute 'lenght'

The last line names the error type and the bad name. The lines above it show the file and line number on your machine, so your path will differ. The ^^^^ marks show which part of the line failed. The correct way to get the length is len(nums).

Practice

Exercise 1. For nums = [1, 2, 0, 1], is the last index reachable? Use the jump game I method and show the value of farthest after each index.

Show the answer

Start with farthest = 0. At i = 0, farthest = max(0, 0 + 1) = 1. At i = 1, 1 <= 1, so farthest = max(1, 1 + 2) = 3. Since 3 >= last, where last is 3, the answer is yes. The values of farthest are 1, then 3.

Exercise 2. For nums = [2, 1, 1, 1, 1], find the fewest jumps needed to reach the last index. Show the values of cur_end and farthest after each jump.

Show the answer

Start with cur_end = 0 and farthest = 0. At i = 0, farthest = 2. Since i == cur_end, jumps = 1 and cur_end = 2. At i = 1, farthest = max(2, 1 + 1) = 2. At i = 2, farthest = max(2, 2 + 1) = 3. Since i == cur_end, jumps = 2 and cur_end = 3. At i = 3, farthest = max(3, 3 + 1) = 4. Since i == cur_end, jumps = 3 and cur_end = 4. The answer is 3. The end is at index 4, so the third jump is the one that reaches it.

Exercise 3. Explain in one or two sentences why the greedy method in jump game II never needs to choose which exact index to land on inside a level.

Show the answer

Every index in one level can be reached with the same number of jumps, so the level's contribution to the next level depends only on the largest reach among its indexes. Choosing the exact landing index does not change that largest reach, so the method only tracks farthest.

Exercise 4. Run can_reach_end by hand on nums = [0, 2] and on nums = [2, 0, 0]. Which one returns True, and why does the other one fail?

Show the answer

For [0, 2], at i = 0 the value is 0, so farthest stays 0. At i = 1, 1 > 0, so the function returns False. For [2, 0, 0], at i = 0, farthest becomes 2, which is at least the last index 2, so the function returns True. The list [2, 0, 0] is the one that returns True. The list [0, 2] fails because index 0 holds 0, and no jump can leave it.

Exercise 5. Predict the output of can_reach_end on nums = [0, 0, 0, 5], then explain your answer in one sentence.

Show the answer

The output is False. At i = 0, farthest stays 0. At i = 1, 1 > 0, so the function returns False before it reads the 5 at the end. Index 0 holds 0, so nothing can move forward from the start.

Summary

• Jump game I tracks farthest, the largest index you can reach. If you reach an index past farthest, the last index is unreachable.
• Reachable indexes form an unbroken block from 0, because each jump covers every index between its start and its end.
• Jump game II counts jumps in levels. cur_end marks the end of the current level, and farthest holds the reach of the next level.
• The sweep for jump game II stops one index before the last, and it stops early once cur_end reaches the last index.
• Test a greedy method against a brute-force search on many small random inputs. Mismatches show the mistakes a single example can hide.