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; } } }