Jump Game II
Jump Game II is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (greedy, one jump per reachable window), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dp over every jump) up.
Problem
You start at index 0 of an integer array nums. The value nums[i] is the longest jump you may make from index i: from there you can move to any index from i + 1 up to i + nums[i].
Return the minimum number of jumps needed to land on the last index. The input always allows reaching it.
Examples
Example 1
- Input
nums = [2, 3, 0, 1, 2, 0, 1]- Output
3- Why
- Jump 0 → 1, then 1 → 4, then 4 → 6. With only two jumps the farthest reachable index is 4.
Example 2
- Input
nums = [1, 1, 1, 1]- Output
3- Why
- Every element only allows a step of one, so each step is a separate jump.
Example 3
- Input
nums = [6]- Output
0- Why
- You already stand on the last index.
Constraints
1 <= nums.length <= 10^40 <= nums[i] <= 1000- The last index is always reachable from index 0.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DP over every jump) | O(n · m) | O(n) |
| Optimal (greedy, one jump per reachable window) | O(n) | O(1) |
1Brute force (DP over every jump)
O(n · m)Each index tries up to m = max(nums[i]) targets.O(n)One array of n jump counts.Let best[i] be the fewest jumps needed to stand on index i. From every index, relax every position it can jump to.
- best[0] = 0, every other entry starts at infinity.
- For i from 0 to n - 1, for every j in i + 1 .. min(n - 1, i + nums[i]): best[j] = min(best[j], best[i] + 1).
- Return best[n - 1].
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] best = new int[n];
Arrays.fill(best, Integer.MAX_VALUE);
best[0] = 0;
for (int i = 0; i < n; i++) {
if (best[i] == Integer.MAX_VALUE) continue;
for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
best[j] = Math.min(best[j], best[i] + 1);
}
}
return best[n - 1];
}
}class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
best = [float("inf")] * n
best[0] = 0
for i in range(n):
if best[i] == float("inf"):
continue
for j in range(i + 1, min(n - 1, i + nums[i]) + 1):
best[j] = min(best[j], best[i] + 1)
return best[n - 1]class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> best(n, INT_MAX);
best[0] = 0;
for (int i = 0; i < n; i++) {
if (best[i] == INT_MAX) continue;
for (int j = i + 1; j <= min(n - 1, i + nums[i]); j++) {
best[j] = min(best[j], best[i] + 1);
}
}
return best[n - 1];
}
};function jump(nums) {
const n = nums.length;
const best = new Array(n).fill(Infinity);
best[0] = 0;
for (let i = 0; i < n; i++) {
if (best[i] === Infinity) continue;
for (let j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
best[j] = Math.min(best[j], best[i] + 1);
}
}
return best[n - 1];
}2Optimal (greedy, one jump per reachable window)
O(n)One pass over the array.O(1)Three integer variables.The indices reachable with exactly k jumps form a window. While scanning that window, record the farthest index any of its positions can reach; that farthest point is the end of the next window. Each time the scan reaches the end of the current window, one more jump is spent.
- jumps = 0, windowEnd = 0, farthest = 0.
- For i from 0 to n - 2: farthest = max(farthest, i + nums[i]).
- If i == windowEnd: jumps++, windowEnd = farthest.
- Return jumps (the loop stops before the last index so no extra jump is counted).
class Solution {
public int jump(int[] nums) {
int jumps = 0, windowEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == windowEnd) {
jumps++;
windowEnd = farthest;
}
}
return jumps;
}
}class Solution:
def jump(self, nums: List[int]) -> int:
jumps = window_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == window_end:
jumps += 1
window_end = farthest
return jumpsclass Solution {
public:
int jump(vector<int>& nums) {
int jumps = 0, windowEnd = 0, farthest = 0;
for (int i = 0; i + 1 < (int) nums.size(); i++) {
farthest = max(farthest, i + nums[i]);
if (i == windowEnd) {
jumps++;
windowEnd = farthest;
}
}
return jumps;
}
};function jump(nums) {
let jumps = 0, windowEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === windowEnd) {
jumps++;
windowEnd = farthest;
}
}
return jumps;
}Edge cases to test
- A single element: the answer is 0
- Zeros in the middle that must be jumped over
- The first element alone reaches the end: the answer is 1
- Always taking the longest jump is not optimal, e.g. [2, 3, 1, 1, 4]
Hints
Hint 1
Think of it as a shortest path: every jump is an edge of weight 1.
Hint 2
All indices reachable with k jumps form one contiguous block. Which block can be reached with k + 1 jumps?
Hint 3
Walk left to right, tracking the end of the current block and the farthest index any position inside it can reach. When you pass the block's end, you must spend one more jump.
FAQ
What is the best time complexity for Jump Game II?
Optimal (greedy, one jump per reachable window) runs in O(n) time and O(1) extra space. One pass over the array.
Which pattern does Jump Game II use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game, Can Place Flowers.
Is there a brute force solution for Jump Game II?
Yes. Brute force (DP over every jump) takes O(n · m) time and O(n) space. Let best[i] be the fewest jumps needed to stand on index i.
Which edge cases should I test for Jump Game II?
A single element: the answer is 0; Zeros in the middle that must be jumped over; The first element alone reaches the end: the answer is 1; Always taking the longest jump is not optimal, e.g. [2, 3, 1, 1, 4].