Java O(n^2) iterative memoization solution using HashMap


  • 1
    K
    public class Solution {
        public boolean canCross(int[] stones) {
            if(stones[1] != 1) return false;
            HashMap<Integer,HashSet<Integer>> h = new HashMap<Integer,HashSet<Integer>>();
            HashSet<Integer> s = new HashSet<Integer>();
            s.add(0);
            h.put(0,s);
            for(int i = 1; i< stones.length;i++)
            {
                for(int j = 0; j< i;j++)
                {
                    if(h.containsKey(stones[j]))
                    {
                        int dis = stones[i] - stones[j];
                        
                        s = h.get(stones[j]);
                        if(s.contains(dis) || s.contains(dis-1) || s.contains(dis+1))
                        {
                            HashSet<Integer> t = new HashSet<Integer>();
                            if(h.containsKey(stones[i]))
                            {
                              t = h.get(stones[i]);
                            }
                             
                            t.add(dis);
                            h.put(stones[i],t);
                        }
                    }
                }
                
            }
            if(h.containsKey(stones[stones.length-1]))
            {
                return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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