Jump Game

The problem

You are given an array nums of numbers (call its length n). You start on index 0. From index i you may jump forward by any distance from 1 up to nums[i]. Return true if you can reach the last index, and false if not.

Example 1

Input: nums = [2, 3, 1, 0, 2, 0, 1]

Output: true

One way: jump 1 to index 1, jump 3 to index 4, jump 2 to index 6.

nums

20311203240516

one path

0 → 1 → 4 → 6

Example 2

Input: nums = [3, 1, 1, 0, 4]

Output: false

Every path lands on index 3, which holds 0. Nothing gets past it.

Example 3

Input: nums = [0]

Output: true

You already stand on the last index.

Constraints

• 1 ≤ n ≤ 10,000
• 0 ≤ nums[i] ≤ 100,000

Clarifying questions

Is nums[i] the exact jump or the most?

The most. Any jump from 1 up to nums[i] is allowed.

Can we jump backward?

No. Jumps only go forward.

Do we need the path or the number of jumps?

No, only whether the last index can be reached.

Is it a problem to jump past the end?

No. A jump that could go further than the last index still reaches it, because a shorter jump is allowed.

Spot the pattern

Because every shorter jump is allowed, the reachable indexes are always one solid block from 0 up to some farthest point. So we never need to track which paths exist, only how far the block goes. One number, updated greedily as we walk, holds all of it. That is the greedy pattern.

Solutions

Mark reachable cellsO(n²)Greedy reachO(n)

Show all

Trying every path with plain recursion is exponential. The marking table below is that same idea, with each index handled once.

Mark reachable cells O(n²)

The idea

Keep a list reachable with one flag per index. At the start only index 0 is reachable. Walk the indexes from left to right. For each reachable index i, mark every index it can jump to as reachable. At the end, read the flag of the last index.

It is correct, because an index is marked only if some reachable index can jump to it. But one index can mark up to n others.

Walkthrough

nums

20311203240516

reachable

TFFFFFF

1. reachable = [False] * len(nums)
2. reachable[0] = True
3. for i in range(len(nums)):
4. if reachable[i]:
5. for j in range(i + 1, min(len(nums), i + nums[i] + 1)): reachable[j] = True
6. return reachable[len(nums) - 1]

reachable[k] says if we can land on index k. Only index 0 is reachable at the start.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Mark reachable cells: each reachable index marks every index it can jump to.
    // One index can mark up to n others, so O(n^2) time and O(n) memory.
    public boolean canJump(int[] nums) {
        int numsLength = nums.length;
        boolean[] reachable = new boolean[numsLength];
        reachable[0] = true;
        for (int i = 0; i < numsLength; i++) {
            // Jumps only count from indexes we can actually stand on.
            if (!reachable[i]) continue;
            // Math.min ignores jumps past the end.
            int last = Math.min(numsLength - 1, i + nums[i]);
            for (int j = i + 1; j <= last; j++) reachable[j] = true;
        }
        return reachable[numsLength - 1];
    }
}

Big O

Time O(n²)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines set one flag. They sit inside two loops: the outer one picks an index, and the inner one marks the indexes it can reach. Setting a flag is 1 step.

   1. reachable = [False] * len(nums)
   2. reachable[0] = True
   3. for i in range(len(nums)):
   4. if reachable[i]:
   5. for j in range(i + 1, min(len(nums), i + nums[i] + 1)): reachable[j] = True
   6. return reachable[len(nums) - 1]

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers. The table shows how many marks each index makes. A jump past the end does not count, so index 6 makes none.

   2 + 3 + 1 + 0 + 2 + 0 + 0 = 8 marks, plus 7 runs of the outer loop.

   i	0	1	2	3	4	5	6
   marks	2	3	1	0	2	0	0

   total

   2 + 3 + 1 + 0 + 2 + 0 + 0 = 8 marks, plus 7 outer runs

3. 3 Write the count for any n

   The worst case is big numbers everywhere. Then index 0 marks n − 1 indexes, index 1 marks n − 2, and so on:

   (n − 1) + (n − 2) + … + 1 = n × (n − 1) / 2

   Check it with Example 1: with big numbers, 7 × 6 / 2 = 21 marks. The real 8 is lower because the jumps are short.

4. 4 Keep only the part that grows fastest

   Drop the ½ and the −½n. What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The reachable list holds one flag per index, so n flags. The space is O(n).

   reachable (n flags)ij

Greedy reach O(n)

The idea

Keep one number, reach: the farthest index we know we can land on. Walk the indexes from left to right.

• If i is past reach, nothing can land on i. We are stuck, so return false.
• Otherwise we can stand on i, so we can reach i + nums[i]. Grow reach if that is farther.

If the walk gets through every index, the last one was reachable.

Why it is correct: every index from 0 to reach can be reached, because shorter jumps are allowed. So the reachable indexes form one block, and reach is its end.

Walkthrough

nums

20311203240516

reach

0

1. reach = 0
2. for i in range(len(nums)):
3. if i > reach:
4. return False
5. reach = max(reach, i + nums[i])
6. return True

reach is the farthest index we can land on so far. Every index up to reach is reachable, because jumps can be shorter than the maximum.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Greedy reach: track the farthest index we can land on. If i ever passes
    // it, we are stuck. One pass, so O(n) time and O(1) memory.
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            // Nothing can land on i, and every later index is even farther.
            if (i > reach) return false;
            // Shorter jumps are allowed, so everything up to reach is reachable.
            reach = Math.max(reach, i + nums[i]);
        }
        return true;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one comparison and one max. That is 1 step. There is one loop.

   1. reach = 0
   2. for i in range(len(nums)):
   3. if i > reach:
   4. return False
   5. reach = max(reach, i + nums[i])
   6. return True

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers. The loop looks at each index once, and reach never falls behind i.

   7 runs.

   i	0	1	2	3	4	5	6
   reach after	2	4	4	4	6	6	7

3. 3 Write the count for any n

   The loop runs once per index, or stops early when it gets stuck:

   at most n runs

   Check it with Example 1: 7 numbers, 7 runs. Example 2 stops at index 4, after 5 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps reach and i. The space is O(1).

   reachi

Common mistake

Stopping at the first zero

A 0 only traps you if you cannot jump over it. In Example 1, index 3 holds 0, but index 1 already reaches index 4. Compare i with reach, do not look for zeros.

Tested at the limits

2,000 random arrays of 1 to 10 jumps from 0 to 3, with many zeros, so traps and ends reached just barely both come up. Mark reachable cells and greedy reach gave the same answer every time.

Largest inputs	Result
10,000 ones (the most allowed), so every index is read. Greedy reach. Also run with a 0 just before the end, a trap at the last step.	Under 0.001 s, and under 0.001 MB of extra memory: just reach and i.
2,000 jumps of 100,000 each. Mark reachable cells.	0.03 s, and about 0.02 MB for the flags. Long jumps make it mark about 2 million cells. At 10,000 it would mark about 50 million.