Listing all paths through a matrix, stepping right or down only

Question

I have the following method, which finds all the possible paths from the top left to bottom right of an N x M matrix. I was wondering what is the best way to optimize it for speed as it is a little slow right now. The resulting paths are then stored in a set.You can only move down or right to an adjacent spot, no diagonals from your current position.

    static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {
        String newString = tempString + arr[i][j];
        if (i == m -1 && j == n-1) {
            palindrome.add(newString);
            return;
        }
        //right
        if (j+1 < n) {
            printPaths (newString, i, j+1, m, n, arr, palindrome);
        }
        //down
        if (i+1 < m) {
            printPaths (newString, i+1, j, m, n, arr, palindrome);          
        }
    }

Answer 1

static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {

You say palindrome? Maybe you shouldn't recycle names from other tasks.

This method should not be public. And should not be called "printWhatever" as it - fortunately - does not print.

arr is an array, nice, but then why did you write "matrix" in your text? Maybe, because of matrix being a more descriptive name? So use it.

The arguments m and n are redundant as they can be obtained from the matrix (and it's improbably more time-consuming than passing them around). Too many arguments make a method hard to use and to read.

So the public method could be

static public Set<String> allPaths(char [][] matrix) {
    Set<String> result = new HashSet<>();
    addAllPathsTo(result, matrix, "", 0, 0);
    return result;
}

with a helper like

static private void addPathsTo(Set<String> result, String tempString, int i, int j, char [][] matrix) {
    String newString = tempString + arr[i][j];
    int m = matrix.length;
    int n = matrix[0].length;
    if (i == m-1 && j == n-1) {
        result.add(newString);
        return;
    }
    //right
    if (j+1 < n) {
        addPathsTo(result, newString, i, j+1, matrix);
    }
    //down
    if (i+1 < m) {
        addPathsTo(result, newString, i+1, j, matrix);
    }
}

The optimization by JS1 makes a lot of sense and could be included. My point was clean up only.

Answer 2

I found a couple of ways to improve your program speed by significant amounts.

Test methodology

First, I ran your original function using a 14x15 matrix. I ran it two times in a row in the same run and timed the second run. It took 31.19 seconds on my machine. I used that as the baseline time to beat.

Use ArrayList instead of HashSet

I'm not sure why you chose to use a HashSet as the container to build your results. Since we are going to presumably just print out all the results sequentially, an ArrayList would be faster because it avoids any unnecessary hashing.

After switching the HashSet to an ArrayList, the time went from 31.19 to 12.80 seconds (2.4x faster).

Using a char [] instead of a String

You can speed up your program by using a char array instead of a String as your temporary string that you build. Something like this:

static public void findPaths (char [] tempPath, int i, int j, int m,
        int n, char [][] arr, ArrayList<String> results) {
    tempPath[i+j] = arr[i][j];
    if (i == m -1 && j == n-1) {
        results.add(new String(tempPath));
        return;
    }
    //right
    if (j+1 < n) {
        findPaths (tempPath, i, j+1, m, n, arr, results);
    }
    //down
    if (i+1 < m) {
        findPaths (tempPath, i+1, j, m, n, arr, results);          
    }
}

You must call the function initially with a char array of size m+n-1. A lot of time in the original function is being spent creating temporary strings. This method avoids all the intermediate strings and only creates the strings that appear in the output.

After switch to a char [] as a temp, the time went from 12.80 to 7.30 seconds (1.75x faster).

Other things I tried that didn't make any difference

I tried a couple of other things that ended up not making any difference in the time.

1. I added "short circuiting" to the code. When either i or j reaches its limit, you can handle that case specially and immediately reach the final cell instead of continuing to recurse.

2. I converted the recursive function into an iterative one.

Both of the above neither hurt nor helped the final time.