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.