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


  • 3
    S

    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;
        }
    }
    

  • 0
    S

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


  • 0
    C

    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.


  • 0
    S

    @coldknight Nice improvement~


  • 0

    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;
        }
    }
    

Log in to reply
 

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