Finding shortest path in matrix

Question

Given an N x N matrix of positive integers, I need to find the shortest path from the first cell of matrix to the last cell of matrix. I can move exactly x steps from any cell, where x is the value of the cell. The possible movements are right or down, i.e from any cell M[i][j] I can move to locations M[i + M[i][j]][j] or M[i][j +M[i][j]].

For example:

int[][] matrix =
    {               
        {1, 2, 1},
        {1, 1, 1},
        {1, 1, 1}
    };

Returning it as a list of strings, the output would be: [(0, 0), (0, 1), (2, 1), (2, 2)]

I have implemented a working solution, but I am wondering if I can improve anything in terms of time complexity?

Here is the code:

class Node {

    // queue node used in BFS
    // (x, y) represents coordinates of a cell in matrix
    int x, y;

    // maintain a parent node for printing final path
    Node parent;

    Node(int x, int y, Node parent) {
        this.x = x;
        this.y = y;
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "(" + x + ", " + y + ')';
    }
}


class Solution {

    LinkedList<String> shortestPathList = new LinkedList<>();

    public List<String> getShortestPath(int[][] matrix) {

        if (matrix == null) {
            return Collections.emptyList();
        }
        Node node = findPath(matrix, 0, 0);                
        AddToPath(node);
        return shortestPathList;
    }



    // possible movements
    private static int[] row = {0, 1};
    private static int[] col = {1, 0};

    // The function returns false if is not a valid position
    private static boolean isValid(int x, int y, int matrixLength) {
        return (x >= 0 && x < matrixLength) && (y >= 0 && y < matrixLength);
    }

    // Find shortest route in the matrix from source cell (x, y) to
    // destination cell (N - 1, N - 1)
    public static Node findPath(int matrix[][], int x, int y) {

        int matrixLength = matrix.length;
        // create a queue and enqueue first node
        Queue<Node> q = new ArrayDeque<>();
        Node src = new Node(x, y, null);
        q.add(src);

        // set to check if matrix cell is visited before or not
        Set<String> visited = new HashSet<>();

        String key = src.x + "," + src.y;
        visited.add(key);

        // run till queue is not empty
        while (!q.isEmpty()) {
            // pop front node from queue and process it
            Node curr = q.poll();
            int i = curr.x, j = curr.y;

            // return if destination is found
            if (i == matrixLength - 1 && j == matrixLength - 1) {
                return curr;
            }

            // value of current cell
            int n = matrix[i][j];

            // check both 2 possible movements from current cell
            // and recur for each valid movement
            for (int k = 0; k < 2; k++) {
                // get next position coordinates using value of current cell
                x = i + row[k] * n;
                y = j + col[k] * n;

                // check if it is possible to go to next position
                // from current position
                if (isValid(x, y, matrixLength)) {
                    // construct next cell node
                    Node next = new Node(x, y, curr);

                     key = next.x + "," + next.y;

                     // if it not visited yet
                     if (!visited.contains(key)) {
                         // push it into the queue and mark it as visited
                         q.add(next);
                         visited.add(key);
                     }
                 }
             }
         }

         // return null if path is not possible
         return null;
     }

     //function to get path from start to end
     private void AddToPath(Node node) {
         if (node == null) {
             return;
         }

         shortestPathList.addFirst(node.toString());
         printPath(node.parent);
     }
}

Answer 1

Access Modifiers & Variables

Firstly, I would recommend you only declare one variable per line. This improves readability and also encourages & facilitates commenting the declarations. It can however have the disadvantage of having an ugly wall of declarations at the start of your classes, though ordering your variables properly can help alleviate this problem.

I personnally like to order class & instance variables like so :

- first, `static final` variables, with a name written in capitals snake_case, e.g. THIS_IS_A_CONSTANT

- then, other `static` variables

- `final` instance variables

- within those, I like placing objects & composite types first, followed by variables of primitive types (`int`, `boolean`, `char` and so on)

- finally, I like having all `public` variables first, then `protected` and finally `private` variables, although I like to put constants at the top whether they are `public` or `private`

Of course, this is only one way of doing it, and some people may think mine is strange or doesn't suit their personal style. I'd recommend you find or come up with one that you like and stick to it in the future.

In practice, it would look something like this :

public class MyClass {
    private static final int SOME_CONSTANT = 25;
    public static final int SOME_OTHER_CONSTANT = 25;   
    public static int aaa;
    public final int A;
    public List<Integer> integers;
    public Object object;
    public int x;   

    ...

    public void someMethod() { ...  }

    private void aPrivateMethod() { ... }

    public static void someOtherMethod() { ... }

    ...

    public int getX() {
        return x;
    }
}

Obviously, the names given to the variables in my example are terrible and I only chose them because I couldn't be bothered to come up with a unique name for each one.

You should also keep all you variable declarations together, and not mix them with method declarations. public variables should be avoided as they can be modified by anyone or anything; instead, you can declare them as private and add getters and/or setters to access them. This can also allow you to add logic inside the getter or setter methods, to check or validate the value provided for example.

For methods, I again like placing all public methods first, followed by protected and then private ones; I generally put static methods at the bottom if there are any. And finally, I like to keep all getters & setters together, somewhere I can easily forget about them after they've been implemented.

Naming and Comments

Your code has a lot of comments, although most of them are superfluous and sometimes even wrong (e.g. run till queue is not empty followed by while (!q.isEmpty())). I personnally don't like comments very much and try to avoid them as much as I can, as they can require a lot of effort to maintain and are often not necessary in well-written code (which I can't claim to write yet, as much as I may want to); I also find that they make the code harder to read when too abundant, and my first instinct when looking at heavily-commented code is often to get rid of all the redundant comments -but that's just me.

But that doesn't mean you shouldn't write comments! However, rather than explaining what the code is doing (which the code itself already does), comments should be used to explain things that cannot be inferred or understood simply by reading the code; for example, telling why one method or technique was used in this particular case rather than another.

As an example, in the snippet below, the comment is only really useful because of how the variable n is named. If it were named nbSteps, or maybe currentValue (I'm not very good with names either, but I'm trying to improve), the comment would then be completely unnecessary. But if you see a reference to n somewhere else is the code, you might think "mmmh, what was n again? was it the size of the matrix? the number of steps I can take? or maybe the number of elements in the queue? who knows!".

// value of current cell
int n = matrix[i][j];

Similarly, the comment // The function returns false if is not a valid position doesn't tell us anything that we don't already know from simply reading the method's name.

This takes us to variable names, and naming in general. Giving your variables, classes and methods meaningful names (that actually tell you what they are or what they do) is probably the most essential thing to making code easy to read. Again, most of your comments simply tell the reader what one things or another is or does, which accomplish very little.

Shortened or abbreviated names like curr or q don't really have any benefit over longer, clearer ones, other than making the very first time you type the name a tiny bit shorter. Renaming them to current and queue for example will make the code easier to read later, and you shouldn't be worried about typing a few more characters each time; let you IDE help you and do its job!

There is probably a lot more to say about comments and maybe JavaDoc, but I think the above outlines enough of the basics to improve your code commenting habits.

I've rewritten your Node class using the above guidelines while keeping its functionality, structure and meaning as close to the original as possible :

Node.java

// queue node used in BFS
public class Node {
    private final int x; // x-coordinate of a cell in matrix
    private final int y; // y-coordinate of a cell in matrix   
    private final Node parent; // maintain a parent node for printing final path

    public Node(final int x, final int y, final Node parent) {
        this.x = x;
        this.y = y;
        this.parent = parent;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public Node getParent() {
        return parent;
    }

    @Override
    public String toString() {
        return '(' + x + ", " + y + ')';
    }
}

I've made all the fields in Node.java private final and added getters, as you don't ever change them after setting them in the constructor. You also used both single and double quotes for characters in your toString() method, which I've corrected.

While trying to refactor and make improvements to your Solution class, I found I was having a hard time understanding how it's meant to be used; at first, I thought it was a static class, from which you call findPath(), which would return... a Node? But you have a mix of static and non-static methods and variables, and use them within one another, but have no constructur...

Also, getShortestPath() returns a list that will only ever contain the node added to it by findPath(), which is simply the lower-right node (or destination, as you call it), so you only ever get the destination and never the actual full path.

I would maybe suggest you refactor this portion of your code and submit it for another review, as -unless I'm mistaken- I do not believe it is actually functional right now.

Some additional things...

I strongly recommend you use the final keyword everywhere you can; method arguments, local variables... it indicates that the value you're assigning to the variable should not and will not change after it's been assigned. In other words, a final variable can only be assigned once, e.g. you can't do final int x = 45; x = 25;.

Again, there's more to say about the use of final, but if you'd like to know more I recommend you take a look at this answer : https://softwareengineering.stackexchange.com/questions/98691/excessive-use-final-keyword-in-java.

I also notice that you didn't include imports in your questions; you should add those next time you ask a question on CodeReview.

You declared an overload for toString() in your Node class, why not use it for the value provided to key? That way, if you ever want to change that key, you can simply change the toString() method instead of having to change it in two places. Or you could create another method just for this purpose, to keep the toString() for displaying a nicely formatted string, while the other one would be a simplified version of your toString(), used solely for generating the 'keys'.

Another thing; you declare shortestPathList as a LinkedList<String>, and getShortestPath() returns a List<String>. I'd suggest you either change shortestPathList's type to a List<String>, or change the method's return type, as it will only ever return shortestPathList. You can find more information about this topic here : https://stackoverflow.com/questions/12321177/arraylist-or-list-declaration-in-java.

If I've made any mistakes or if you disagree with anything I've said, please refrain from throwing your keyboard at me but do point them out to me so that I can improve my own skills and knowledge!