Very easy to understand JAVA solution with explanations


  • 47
    Q

    Use map to represent a mapping from the stone (not index) to the steps that can be taken from this stone.

    so this will be

    [0,1,3,5,6,8,12,17]

    {17=[], 0=[1], 1=[1, 2], 3=[1, 2, 3], 5=[1, 2, 3], 6=[1, 2, 3, 4], 8=[1, 2, 3, 4], 12=[3, 4, 5]}

    Notice that no need to calculate the last stone.

    On each step, we look if any other stone can be reached from it, if so, we update that stone's steps by adding step, step + 1, step - 1. If we can reach the final stone, we return true. No need to calculate to the last stone.

    Here is the code:

        public boolean canCross(int[] stones) {
            if (stones.length == 0) {
            	return true;
            }
            
            HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(stones.length);
            map.put(0, new HashSet<Integer>());
            map.get(0).add(1);
            for (int i = 1; i < stones.length; i++) {
            	map.put(stones[i], new HashSet<Integer>() );
            }
            
            for (int i = 0; i < stones.length - 1; i++) {
            	int stone = stones[i];
            	for (int step : map.get(stone)) {
            		int reach = step + stone;
            		if (reach == stones[stones.length - 1]) {
            			return true;
            		}
            		HashSet<Integer> set = map.get(reach);
            		if (set != null) {
            		    set.add(step);
            		    if (step - 1 > 0) set.add(step - 1);
            		    set.add(step + 1);
            		}
            	}
            }
            
            return false;
        } 
    

  • 10

    I think it's better to add the following line at the top of your code.

    // the most progressive arrange is [0, 1, 3, 6, 10, 15, 21, ...]
    // the right-most point is at most 0 + (1 + len - 1) * (len - 1) / 2
    if(stones == null || stones.length == 0 || stones[1] != 1 ||
                    stones[stones.length - 1] > (stones.length * (stones.length - 1)) / 2) return false;
    

  • 0
    C

    Similar idea, I chose arraylist instead of map (map is better i tihnk), also I think we don't need loop to the stones.length, when current is already bigger than the reach, can prune mostly but still same in worst case.

    public boolean canCross(int[] stones) {
        if(stones.length==2) return stones[1]-stones[0]==1;
        List<HashSet<Integer>> dp = new ArrayList<>(stones.length);
        for(int i=0;i<stones.length;i++)
            dp.add(new HashSet<Integer>());
    
        Iterator<Integer> kSet;
        dp.add(1, new HashSet<>(Arrays.asList(1)));
    
        for(int i=2;i<stones.length;i++){
            kSet = dp.get(i-1).iterator();
            int j=i, k=-1;
            while((k!=-1||kSet.hasNext())&&j<stones.length){
    
                if(k==-1) k = kSet.next();
                if(Math.abs(stones[j]-stones[i-1]-k)<=1)  //k reach point
                {
                    if(j == stones.length-1) return true;
                    HashSet<Integer> temp = dp.get(j);
                    temp.add(stones[j]-stones[i-1]);
                }
                else if (j == stones.length-1||stones[j]-stones[i-1]-1>k)
                    {k=-1;j=i-1;}
                j++;
    
            }
    
        }
        return false;
    }

  • 2
    S

    What's the time complexity ?


  • 0
    P

    @quincyhehe great solution. would this solution become to "greedy" approach?


  • 1
    S

    Is the time complexity O(N^2)?


  • 0
    J

    @quincyhehe similary, but slow and got TLE.

     public boolean canCross(int[] stones) {
            int n=stones.length;
            List[]dp=new ArrayList[n];
            for(int i=0;i<n;i++){
                dp[i]=new ArrayList<Integer>();
            }
            if(1!=stones[1]) return false;
            dp[1].add(1);
            for(int i=1;i<n;i++){
                for(int step: (ArrayList<Integer>)dp[i]){
                    int temp=step;
                    for(int j=-1;j<=1;j++){
                        temp=step+j;
                        if(temp>0){
                             int index=Arrays.binarySearch(stones,i,n,stones[i]+temp);
                             if(index>=0){
                                if(index==n-1) return true;
                                dp[index].add(temp);
                             }
                        }
                       
                    }
                }
            }
            return !dp[n-1].isEmpty();
        }
    `````````````````````

  • 0
    Z

    @quincyhehe So, what's the time complexity?


  • 0
    I

    Great Solution. In C++ for reference,

        bool canCross(vector<int>& stones) {
            
            unordered_map<int, unordered_set<int>> hm;
            
            for(stone : stones)
            {
                hm[stone] = unordered_set<int>{};
            }
            hm[stones[0]].insert(1);
          
            int target = stones[stones.size()-1];
            
            for(int i = 0; i < stones.size()-1; i++)
            {
                int stone = stones[i];
                for(step : hm[stone])
                {
                    int reach = stone + step;
                    if(stone + step == target)
                    {
                        return true;
                    }
                    if(hm.count(reach))
                    {
                        hm[reach].insert(step);
                        hm[reach].insert(step+1);
                        if(step > 0) hm[reach].insert(step-1);
                    }
                }
            }
            
            return false;
        }
    

  • 0
    H

    So what's the time complexity of this solution? It looks like O(n)


  • 3

    @ZhuEason said in Very easy to understand JAVA solution with explanations:

    @quincyhehe So, what's the time complexity?

    The time complexity is O(n2).

    Slightly modified the example in the original post -
    [0 , 1, 3, 5, 6, 8, 10 ...]
    As more stones are added, the size of HashSet at each stone grows.
    The list after the each stone represents the options for the next jump.

    {0=[1], 1 = [1, 2], 3 = [1, 2, 3], 5 = [1, 2, 3], 6 = [1, 2, 3, 4], 8 = [1, 2, 3, 4 ], 10 = [1, 2, 3, 4, 5 ]... }

    The size of HashSet at each stone won't be big than n (n is the total number of stones), since there is at most one way to directly jump from a previous stone to the current one.


  • 0
    R

    What a happy co-incidence. I wrote same solution but using LinkedHashMap.
    I recommend to use LinkedHashMap instead of either HashMap, because it will not guarantee insertion order, or ArrayList which doesn't look clean. Here is my code

    // Time : O(n), Space : O(n)
    	public static boolean canFrogJumpToEnd(int[] stones) {
    		Map<Integer, HashSet<Integer>> map = new LinkedHashMap<>();
    		for (int num : stones) {
    			map.put(num, new HashSet<>());
    		}
    		map.get(0).add(1);
    		for (Integer num : map.keySet()) {
    			for (Integer val : map.get(num)) {
    				List<Integer> reach = new ArrayList<Integer>();
    				if (val > 1)
    					reach.add(val - 1);
    				reach.add(val);
    				if (num != 0)
    					reach.add(val + 1);
    				for (int step : reach) {
    					if (map.containsKey(num + step)) {
    						if (num + step == stones[stones.length - 1])
    							return true;
    						map.get(num + step).add(step);
    					}
    				}
    			}
    		}
    		return false;
    	}
    111

  • 0

    @raj29

    Wondering why LinkedHashMap is preferable here.
    We have to traverse all of the steps in the HashSet at each stone anyway, so it doesn't seem to matter which step in the HashSet goes first, and which second.
    Moreover, if you use LinkedHashMap, there is extra expense of maintaining the underlying LinkedList when doing put()/get().


  • 0
    R

    @zzhai
    As mentioned, we need to maintain the order while HashMap do not assure the order. That's why others had to use either ArrayList or existing array again in addition to hash map while iteration.


  • 0

    @raj29

    Ok, cool. You used a different type of for loop.


  • 0

    @raj29 If you're using LinkedHashMap to be able to use a for each loop in the outer loop and not depend on int[] stones, then you can process the results in another function where int[] stones is no longer in scope:

    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> stonesToSteps = new LinkedHashMap<>(stones.length);
        for (int stone : stones) stonesToSteps.put(stone, new HashSet<Integer>());
        stonesToSteps.get(0).add(1);
        
        return canCross(stonesToSteps, stones[stones.length - 1]);
    }
    
    private boolean canCross(Map<Integer, Set<Integer>> stonesToSteps, int lastStone) {
        BiConsumer<Set<Integer>, Integer> addSteps = (steps, step) -> {
            steps.add(step);
    	steps.add(step + 1);
    	if (step - 1 > 0) steps.add(step - 1);
        };
        
        for (int stone : stonesToSteps.keySet()) {
        	for (int step : stonesToSteps.get(stone)) {
                int reach = step + stone;
        	    if (reach == lastStone) return true;
        	    if (stonesToSteps.containsKey(reach)) addSteps.accept(stonesToSteps.get(reach), step);
        	}
        }
        
        return false;
    }
    

  • 1
    D

    I used depth first search. In each node searched, I only proceed when that node is reachable from start. Then I check results from next three possible jumps.

    The complexity is O(3^n). But with cache, it goes down to O(n). My solutions runs within 15ms.

    l1                                        n1(2,3,4)
    l2              n2(1,2,3)                 n3(2,3,4)                n4(3,4,5)          
    l3                       ....                            n11(2,3,4) n12(3,4,5) n13(4,5,6)
     ...
    ln
    

    Notice that at each level, only one new value is added.

    public class Solution {
        Map<Integer, Integer> posToIdx=new HashMap<>();
        Map<Integer,Map<Integer, Boolean>> cache = new HashMap<>();
        public boolean canCross(int[] stones) {
            int max = stones.length * (stones.length -1) /2;
            if (stones[stones.length-1] > max) return false;
            
            for (int i=0;i<stones.length;i++) {
                posToIdx.put(stones[i], i);
            }
            return dps(1, stones, 1);
        }
        
        boolean dps(int k, int[] stones, int pos) {
            // test reachable to current pos
            if (!posToIdx.containsKey(pos)) {
                return false;
            }
            // reachable
            
            // now check if it can reach to the end
            // already at the end
            if (posToIdx.get(pos) == stones.length-1) return true;
            
            // check cache first
            Map<Integer, Boolean> byIdx = cache.getOrDefault(k, new HashMap<>());
            int idx = posToIdx.get(pos);
            if (byIdx.containsKey(idx)) {
                return byIdx.get(idx);
            }
            
            if (dps(k+1, stones, pos + k + 1)) {
                byIdx.put(idx, true); 
                return true;
            }
            
            if (dps(k,stones, pos+k)) {
                byIdx.put(idx, true); 
                return true;
            }
            
            if (k-1>0 && dps(k-1, stones, pos+k-1)) {
                byIdx.put(idx, true); 
                return true;
            }
            byIdx.put(idx, false); 
            return false;
        }
    }
    

  • 0
    S

    Can someone please explain what is the meaning of "steps that can be taken from this stone."?

    To my understanding, at stone0 frog can only jump 1 steps, so 0=[1]. At stone1, frog can jump 0, 1, or 2 steps, but why 1=[1, 2]?


  • 0

    @seaeidolon

    A frog certainly can jump 0 step at stone 1, and stays at the same stone this way. How would that help resolve the problem though? It has no impact on the following stones.


  • 0
    This post is deleted!

Log in to reply
 

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