Jump Game II — Solution in Python, Java & C++
Jump Game II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Jump Game II is a medium coding problem on arrays, dynamic programming and greedy, asked in Atlassian and PhonePe interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Greedy
- Asked at: Atlassian, PhonePe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You start at index 0 of array nums, where nums[i] is the maximum jump length from i. Return the minimum number of jumps to reach the last index. The tests guarantee you can always reach it.
Example 1
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Index 0 → 1 → 4.
Example 2
Input: nums = [2,3,0,1,4]
Output: 2
Constraints
1 <= nums.length <= 301 <= nums[i] <= 5Reaching the last index is always possible.
Hints for Jump Game II
Hint 1
Think in BFS levels: everything reachable in j jumps forms a window.
Hint 2
When you walk past the current window's end, you must take another jump.
How to solve Jump Game II
Think of it as breadth-first search on a line. Everything you can reach in exactly one jump forms a contiguous window; everything reachable in two jumps forms the next window, and so on. You never need a queue — just track where the current window ends and how far the next one will stretch.
Approach
- Track
jumps,curEnd(the last index of the current window) andfarthest(the furthest index reachable from anything seen so far). - Walk
ifrom0up to but not including the last index. - Update
farthest = max(farthest, i + nums[i]). - When
i == curEnd, you have exhausted the current window: take a jump, and let the next window end atfarthest. jumpsis the minimum count when the walk finishes.
Why it works
This is BFS with the levels collapsed into indices. Reachability from a window is monotone — the union of what its members reach is itself a contiguous range ending at farthest — so a level is fully described by its endpoint. Since BFS visits nodes in non-decreasing distance, the level at which the last index first falls inside the window is its shortest jump count.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Stop the loop before the last index. Including it counts one jump too many when the last index happens to close a window.
- Bump
jumpswhenireachescurEnd, not whenireachesfarthest. - A single-element array needs
0jumps, which falls out because the loop never runs.
Reference solution
Python
from typing import List
def jump(nums: List[int]) -> int:
jumps = 0
end = 0
far = 0
for i in range(len(nums) - 1):
far = max(far, i + nums[i])
if i == end:
jumps += 1
end = far
return jumpsJava
public static int jump(int[] nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i + 1 < nums.length; i++) {
if (i + nums[i] > farthest) farthest = i + nums[i];
if (i == curEnd) {
jumps++;
curEnd = farthest;
}
}
return jumps;
}C++
int jump(vector<int>& nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i + 1 < (int) nums.size(); i++) {
if (i + nums[i] > farthest) farthest = i + nums[i];
if (i == curEnd) {
jumps++;
curEnd = farthest;
}
}
return jumps;
}JavaScript
var jump = function(nums) {
let jumps = 0, end = 0, far = 0;
for (let i = 0; i < nums.length - 1; i++) {
far = Math.max(far, i + nums[i]);
if (i === end) {
jumps++;
end = far;
}
}
return jumps;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming