# 60ms Java O(N^2) use a matrix for memorization

• memo[i][j] = 1 means that the frog can reach the final destination from i-th stone, with j being the previous step size. Because the maximum previous step size for the 0th, 1th, 2th stone is 0, 1, 2, ... , which means the maximum j is equal to i. So we can declare the matrix size as n*n where n is the number of stones.

If ignoring the recursive call overhead, this algorithm should have a time complexity of O(n^2) because we are just filling half of this matrix memo.

``````public class Solution {
public boolean canCross(int[] stones) {
if(stones[1] != 1) return false;
int n = stones.length;
int[][] memo = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
{
memo[i][j] = -1;
}
}

return canCross(stones, 0, 0, memo, n);
}
private boolean canCross(int[] stones, int i, int j, int[][] memo, int n) {
if(memo[i][j]!=-1) return memo[i][j] == 1;
if(i == n - 1) {
memo[i][j] = 1;
return true;
}

for(int k = i + 1; k < n; k++) {
if(stones[k] < j - 1 + stones[i]) continue;
else if(stones[k] > j + 1 + stones[i]) {
memo[i][j] = 0;
return false;
}
else {
if(canCross(stones, k, stones[k] - stones[i], memo, n)) {
memo[i][j] = 1;
return true;
}
}
}
memo[i][j] = 0;
return false;
}
}
``````

• @seedlingfl Actually it is 46 ms... I don't know how to edit the title...

• Nice solution. It's better than map memorization. It is 34 ms after using -1 as false rather than 0 to avoid array initialization. I tried to replace for(int k = i + 1; k < n; k++) loop by binary search or index map. However, it didn't improve run time any more.

• @coldknight Nice improvement~

• Same idea, one less round by using null.

``````class Solution {
public boolean canCross(int[] stones) {
if(stones.length < 2)
return true;
if(stones[1] - stones[0] != 1)
return false;
Boolean[][] mem = new Boolean[stones.length][stones.length];
return canCross(stones, 1, 1, mem);
}

private static boolean canCross(int[] s, int p, int k, Boolean[][] mem) {
if(mem[p][k] != null)
return mem[p][k];
if(p == s.length - 1) {
mem[p][k] = true;
return true;
}
for(int i = p+1;i<s.length;++i) {
if(s[i] < s[p] + k - 1)
continue;
if(s[i] > s[p] + k + 1)
break;
if(canCross(s, i, s[i] - s[p], mem))
return true;
}
mem[p][k] = false;
return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.