Jump Game II
Problem link: https://leetcode.com/problems/jump-game-ii/
Problem Statement
You are given an array nums where nums[i] is the maximum jump length from index i.
Starting at index 0, return the minimum number of jumps needed to reach the last index.
Input
nums: integer array
Output
- Minimum jumps to reach
n - 1
Example
nums = [2, 3, 1, 1, 4]
output = 2
Explanation
Jump 0 -> 1, then 1 -> 4.
Brute Force
Intuition
If we know the best answer to reach smaller indices, we can build the best answer for later indices.
Approach
Let dp[i] be the minimum jumps to reach index i.
For each i, try all j < i that can reach i.
Code (Java)
Time: O(N^2)Space: O(N)
Complexity Analysis
- Time
O(N^2): for everyi, you scan all earlierj. - Space
O(N): the DP array stores answers for all indices.
Optimal Solution
Intuition
Every index you can reach with k jumps forms a range.
From that range, one more jump can expand to a new range.
Track:
currentEnd: end of the current jump rangefarthest: farthest index reachable from within the current range
Approach
Scan once, maintaining the current “level” end.
Code (Java)
public class JumpGameIIOptimal {
public static int jump(int[] nums) {
int n = nums.length;
if (n <= 1) return 0;
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
// We reached the end of the current jump range: take a jump.
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
}
Time: O(N)Space: O(1)
Complexity Analysis
- Time
O(N): each index is processed once. - Space
O(1): only a few pointers/counters are used.
Quick Revision (Brute Force)
- DP: dp[i] = min jumps to i; try all j<i that can reach i.
- Simple but slow for large N.
- Time O(N^2), Space O(N).
Quick Revision (Optimal)
- Greedy BFS-level view: currentEnd is current range, farthest is next range.
- When i hits currentEnd, take a jump and extend to farthest.
- Time O(N), Space O(1).