BFS to check if path from start node to end node exists

Question

I'm trying to solve a problem from leetcode called Jump Game and it seems to be a pretty simple graph problem where we have to find if a path exists from a start node to an end node. I personally always struggle with problems like this, where graphs are represented as arrays (instead of a Node class with connections) so I would appreciate a review of the code I wrote. My current solution looks as follows:

class Solution {

    public boolean canJump(int[] nums) {

        if(nums.length == 1)
            return true;

        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();

        for(Integer i = 0; i < nums.length; i++) {

            ArrayList<Integer> edges = new ArrayList<Integer>();

            int jumps = nums[i];

            if (jumps != 0) {
                for(Integer j = 1; j <= jumps; j++) {
                    edges.add(i+j);
                }
            } else {
                edges.add(-1);
            }

            graph.put(i, edges);
        }

        //we have our graph ready

        Integer target = nums.length - 1;
        System.out.println("target is : " + target);

        HashSet<Integer> visited = new HashSet<Integer>();


        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(0);

        while(!queue.isEmpty()) {
            System.out.println("queue " + queue.peek());
            visited.add(queue.peek());
            ArrayList<Integer> edges = graph.get(queue.poll());

            System.out.println("edges is : " + edges);

            for(Integer edge : edges) {

                if(!visited.contains(edge)){

                    if (edge == target) {
                        return true;
                    }

                    if(!queue.contains(edge) && edge > 0){
                        queue.add(edge);
                    }
                }
            }

        }

        return false;

    }

}

So firstly, I know I'm doing some redundant operations. Right now I am creating a HashMap to store my graph in Node->ConnectionsList pairs since its just easier for me to visualize. I know I can just skip doing this and just directly use the input array and a queue to run my search, and I will be optimizing this later.

I would mostly like someone to go over my BFS logic implementation (in the while loop) and let me know if there is anything logically wrong with my code for it.

As it stands I pass 73/75 test cases on leetcode because of a time out, but I'd like to make sure my BFS logic is sound before I continue. There seems to be another easier way to solve this problem without BFS, but for now I'm using this to practice implementing graph search algorithms so I'd appreciate a review of that portion.

Answer 1

Notes:

1. You should strive to keep the left-hand side type as general as possible. That means HashMap<Integer, ArrayList<Integer>> graph should be Map<Integer, List<Integer>> graph.
   This is preferrable to enable simple substitution of implementations.
   For more information why that's useful, look up the "Liskov Substitution Principle"

   The same considerations apply for edges and visited, though interestingly not for queue.

2. It's significantly easier for the compiler and the JVM to iterate with an int counter and not an Integer counter, because the latter requires unboxing and boxing on every single operation you perform.

3. Your algorithm only performs forward jumps. While the implications of the problem itself, as well as the fact that you're actually checking every single node that's reachable forward mean that you never have to consider backward jumps, that is problematic for general graph searches.

4. You can save a ton of time by implementing the Queue with a TreeSet. Using a Set prevents duplicate iterations, which you currently do not. You should also be able to get a lot of speed out of "greedily" searching, by jumping as far ahead as you possibly can in each step.

Note that what I said in 4 also should give you a hint as to how you can solve the problem without using a graph-search.