3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the helpful response @Vogel612 . I wasn't aware of points 1 and 2, so I'll try to rewrite my code to reflect those. Could you explain what unboxing and boxing means with regards to using an Integer? For point 3, since the problem is very vague, I just assumed that I would have to consider forward jumps only. If I wanted to consider backwards jumps, would I just add the backwards indexes (ie. i-j assuming its valid) into my HashMap? Or would there be something I do in my actual search loop? \$\endgroup\$ – FlameDra Feb 19 '18 at 19:02
  • \$\begingroup\$ For point 4, I wasn't aware of the fact that I can implement a Queue with a TreeSet as all the examples I found were using a Linked List. Could you explain how I can greedily search? Do I just go the max jump from index 0, and the max jump from the index I land on, and so on. and check if I reach my target? If I don't reach my target, how would I implement the logic to go back and check other possible routes? Sorry if I sound a bit lost. \$\endgroup\$ – FlameDra Feb 19 '18 at 19:04
  • \$\begingroup\$ re 3: for the given problem, you're fully correct. I also explicitly state that that's not a problem in my answer. Yes your first assumption is correct, you'd need to avoid infinite loops, though. Re the fourth point: Currently your Queue in combination with the visited set has the same behaviour as a PriorityQueue that prioritizes the minmal value as highest, which is very nicely implemented as a TreeSet that's ordered by inverse value. While it does not conform to the Queue interface itself, you only use a limited subset of that interface, which can be directly mapped to a TreeSet \$\endgroup\$ – Vogel612 Feb 19 '18 at 22:38
  • \$\begingroup\$ Last but not least: I don't want to tell you how it works, because that'd rob you of the learning experience, but greedily searching works by attempting to make the largest steps possible. Since the problem directly implies that all previous steps can be reached, you can backtrack pretty easily. You just need to keep track of where you already backtracked through and go back one index at a time, trying to advance beyond your "current best". That should be enough tips, to get a working solution :) I'll be happy to review that in a follow-up question :) \$\endgroup\$ – Vogel612 Feb 19 '18 at 22:41
  • \$\begingroup\$ I think I figured out the greedy approach to solving this, and leetcode accepts the answer link. I do want to improve on my bfs solution though, since I want to practice writing graph search algorithms. Let me know if you get a change to have a look. \$\endgroup\$ – FlameDra Feb 20 '18 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.