class Solution {
    public boolean canCross(int[] stones) {
        /* Q64 of dp playlist , in this question we need to store the jumps which
        has been made from the previous stone for that we make a HM<stones , HS>
        to store the allowed jumps

        we traverse the array and keep updating the next stones allowed jumps,
        if we end up on any stone which has its jumps hashset = 0 we return false
        if we end on last stone we return true;
        */
    
        //make a hashmap to store allowed jumps
        HashMap<Integer,HashSet<Integer>> map = new HashMap<>();
        int n = stones.length;

        //fill the hashmap and initialise the HS
        for(int i = 0 ; i < n ; i++)
        map.put(stones[i] , new HashSet<>());

        //adding jumps for 0th and 1st stone;
        map.get(0).add(1);
        
        //traverse the array
        for(int i = 0 ; i < n ; i++){
            
            //taking out allowed jumps
            HashSet<Integer> jumps = map.get(stones[i]);

            //check all jumps in jumps hashset
            for(int jump : jumps){
                System.out.print(" " + stones[i] +" "+ jump+ "\n" );
                
                boolean validJump = map.containsKey(stones[i] + jump);
                
                //if after jumping we end on a valid stone update the jumps of 
                //the valid stone 
                if(validJump == true){
                    HashSet<Integer> nextStone = map.get(stones[i] + jump);

                    nextStone.add(jump);
                    nextStone.add(jump + 1);
                    
                    //we cannot add 0 jumps
                    if(jump != 1)
                    nextStone.add(jump - 1);

                    map.put(stones[i] + jump , nextStone);
                    
                }
            }
        }

        if(map.get(stones[n-1]).size() > 0){
            // System.out.println(map);
            return true;
        }

        else{
            // System.out.println(map);
            return false;
        }
        
    }
}