# java dp solution, only use array, 15ms

• Record the minimal and maximal possible next step at each stone, and move forward.

``````
public class Solution {
public boolean canCross(int[] stones) {
if (stones.length <= 1){
return true;
}
int n = stones.length;
int[] minNextStep = new int[n];
int[] maxNextStep = new int[n];
Arrays.fill(minNextStep, Integer.MAX_VALUE);
minNextStep[0] = 1;
maxNextStep[0] = 1;
for (int i = 0; i < n; i++){
if (minNextStep[i] > maxNextStep[i]){
return false;
}
int j = i + 1;
for (int k = Math.max(1, minNextStep[i]); k <= maxNextStep[i]; k++){
if (j >= n){
break;
}
if (stones[i] + k < stones[j]){
continue;
} else if (stones[i] + k == stones[j]){
minNextStep[j] = Math.min(minNextStep[j], k - 1);
maxNextStep[j] = Math.max(maxNextStep[j], k + 1);
j++;
} else{
j++;
}
}
}
return true;
}
}
``````

• This method fails in this case: `[0,1,3,6,10,13,15,16,19,21,25]`, which should return false, while this method returns true. Because only storing min and max step might miss some information. For example, at ith stone, we might only has possible previous step length 1-3 and 5-6, while this method simply combine them as 1-6. @1337c0d3r

• This post is deleted!

• This method fails in this case: `[0,1,3,6,10,13,15,16,19,21,25]`, which should return false, while this method returns true. Because only storing min and max step might miss some information. For example, at ith stone, we might only has possible previous step length 1-3 and 5-6, while this method simply combine them as 1-6.

Nice catch, there are so many problem with not enough test cases