Java DP solution O(n^2) and Recursion using memorization


  • 0
    S

    For the DP code, the time cost is high. It just fairly past the tests. The time complexity is O(n^2). Not clear why it takes so long

        //DP
        public boolean canCross(int[] stones) {
            if (stones.length == 2) return stones[1] == 1;
            //Map[stone]:all possible previous steps to reach this stone
            Set<Integer>[] myMap = new HashSet[stones.length];
    
            //first stone
            myMap[0] = new HashSet<Integer>();
            //first can be reach with last step size 1
            myMap[0].add(0);
    
            
            for (int i = 1; i < stones.length; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    //if stone j can not be reached
                    if (myMap[j] == null)continue;
                    
                    //Since the stone is sorted, if last steps needed to reach stone i is larger than the maximum
                    //possible steps needed to reach j, break.
                    int step = stones[i] - stones[j];
                    if (step > stones[j] + 1) break;
                    
                    //if the stone i can be reached from stone j, uppdate stone i
                    if (myMap[j].contains(step) || myMap[j].contains(step - 1) || 
                        myMap[j].contains(step + 1)) {
                        if (myMap[i] == null) myMap[i] = new HashSet<Integer>();
                        myMap[i].add(step);
                    }
                    
                }
               
            }
            
            return myMap[stones.length - 1] != null;
        }  
    

    Recursion: Time lime exceed. Do not know why....It seems I used similar idea as others....

     Recursion with memory
    
        public boolean canCross(int[] stones) {
            Set<Integer>[] myMap = new HashSet[stones.length];
            
            return helper(myMap, stones, 0, 0);
            
        }
        
        public boolean helper(Set<Integer>[] myMap, int[] stones, int start, int preStep) {
            if (myMap[start] != null && myMap[start].contains(preStep)) return true;
            
            for (int next = start + 1; next < stones.length; next++) {
                int gap = stones[next] - stones[start];
                if (gap < preStep - 1) continue;
                if (gap > preStep + 1) return false;
                if (helper(myMap, stones, next, gap)) {
                    if (myMap[start] == null) myMap[start] = new HashSet<Integer>();
                    myMap[start].add(preStep);
                    return true;
                }
            }
            
            if (start == stones.length - 1) {
                if (myMap[start] == null) myMap[start] = new HashSet<Integer>();
                myMap[start].add(preStep);
                return true;
            }
            
            return false;
        }
    

Log in to reply
 

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