Question
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Stats
| Frequency | 2 |
| Difficulty | 4 |
| Adjusted Difficulty | 3 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Solution
This is a DP problem. But we do not have to save all values into a DP array.
A analysis of DP solution from this blog explains it very well:
Search forward, and see for each node of array, what is the current maximum place we can reach, and every time we reach a local maximum, we add counter by 1, if we can reach the terminal, just return the counter.
It’s easy to get “time limit exceed” if you solve this problem like a traditional DP question.
So I come up with a solution using 2 pointers: ‘left’ and ‘right’ that denotes the boundary that can be jumps to within a certain number of jumps. What I need to do is updating the 2 pointers and increase the counter for number of jumps.
My code
traditional DP
public class Solution {
public int jump(int[] A) {
int len = A.length;
if (len <= 1) return 0;
int[] dp = new int[len];
if (A[0] == 0) return 0;
int cur = 1;
for (int i = 0; i < len; i ++) {
if (i != 0 && dp[i] == 0)
return 0;
// array dp represent the steps to reach point i
for (; cur < len && cur <= i + A[i]; cur ++) {
dp[cur] = dp[i] + 1;
}
if (dp[len - 1] != 0)
return dp[len - 1];
}
return 0;
}
}
DP without array (recommended)
public class Solution {
public int jump(int[] A) {
if (A == null || A.length <= 1) {
return 0;
}
int len = A.length;
// note that this is a DP question, but considering the required out,
// we do not need dp array (i.e.)
// int[] dp = new int[len];
int jumps = 0;
int left = 0;
int right = 0;
while (right < len) {
int reachable = right;
jumps++;
for (int i = left; i <= right; i++) {
reachable = Math.max(reachable, i + A[i]);
}
if (reachable == right) {
// unable to jump forward
return -1;
}
if (reachable >= len - 1) {
return jumps;
} else {
left = right + 1;
right = reachable;
}
}
return -1;
}
}
non-DP
public class Solution {
public int jump(int[] A) {
if (A == null || A.length <= 1) {
return 0;
}
int len = A.length;
// note that this is a DP question, but considering the required out,
// we do not need dp array (i.e.)
// int[] dp = new int[len];
int jumps = 0;
int left = 0;
int right = 0;
while (right < len) {
int reachable = right;
jumps++;
for (int i = left; i <= right; i++) {
reachable = Math.max(reachable, i + A[i]);
}
if (reachable == right) {
// unable to jump forward
return -1;
}
if (reachable >= len - 1) {
return jumps;
} else {
left = right + 1;
right = reachable;
}
}
return -1;
}
}