Java Solution, Could not figure out time complexity. Please help me.


  • 0
    B
    public class Solution {
    public boolean canCross(int[] stones) {
        int len = stones.length;
        if(len < 2) return false;
        Map<Integer,Set<Integer>> stonePowers = new HashMap<>();
        for(int i = 0; i < len; i++) stonePowers.put(stones[i],new HashSet<>());
        stonePowers.get(0).add(1);
        int goal = stones[len-1];
        for(int i = 0; i < len -1; i++){
            for(Integer k : stonePowers.get(stones[i])){
                if(stones[i] <= Integer.MAX_VALUE-k && stonePowers.containsKey(stones[i]+k)){
                    if(stones[i]+k == goal){
                        return true;
                    }
                    if(stones[i]+ k <= Integer.MAX_VALUE-k+1 && k-1 >0)
                        stonePowers.get(stones[i]+k).add(k-1);
                    if(stones[i]+ k <= Integer.MAX_VALUE-k && stones[i]+2*k <= goal)
                        stonePowers.get(stones[i]+k).add(k);
                    if(stones[i]+ k <= Integer.MAX_VALUE-k-1 && stones[i]+2*k+1 <= goal)
                        stonePowers.get(stones[i]+k).add(k+1);
                }
            }
        }
        return false;
    }
    

    }


Log in to reply
 

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