Find total number of paths in a matrix of 0's and 1's

Question

I am working on a program which states that:

You are given a 2-D matrix with M rows and N columns.You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1’s and 0’s. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through that cell. Return the number of paths from top-left cell to bottom-right cell.(i.e. (0,0)to(M-1,N-1)). Since answer can be large thus you have to return ans%(10^9+7).

static int count(int a[][], int i, int j) {
    int rows = a.length;
    int cols = a[0].length;
    if(a[i][j] == 0)  return 0;
    if (i == rows - 1 && j == cols - 1)
        return a[i][j];
    else if (i == rows - 1)
        return a[i][j + 1];
    else if (j == cols - 1)
        return a[i + 1][j];
    else if (a[i][j] == 1)
        return count(a, i + 1, j) + count(a, i, j + 1);
    else
        return 0;
}

How can we improve the performance of this program?

Answer 1

Recursion is not recommended. First, you would likely end up repeating calculations for cells that are approached from multiple paths. Second, the call stack would be as deep as the longest path, and you could easily crash with a StackOverflowError for a large maze.

Instead, I recommend using dynamic-programming, building a 2D table where each entry is the number of paths from the start to that location. Every paths[r][c] is calculated exactly once, and in an order that is gentle to the cache.

public static int count(int[][] a) {
    int[][] paths = new int[a.length][a[0].length];
    if ((paths[0][0] = a[0][0]) == 0) {
        return 0;
    }
    for (int c = 1; c < a[0].length; c++) {
        paths[0][c] = a[0][c] * paths[0][c - 1];
    }
    for (int r = 1; r < a.length; r++) { 
        paths[r][0] = a[r][0] * paths[r - 1][0];
        for (int c = 1; c < a[r].length; c++) {
            paths[r][c] = a[r][c] * (paths[r - 1][c] + paths[r][c - 1]);
        }
    }
    return paths[a.length - 1][a[0].length - 1];
}

You can even even build the paths one row at a time, while the maze a is being loaded. Furthermore, it is possible to modify the code to use less memory, since only the last two rows of paths are relevant at any given time. However, for simplicity, I haven't done that here: if you can afford to keep the entire a in memory, then you can probably also afford to keep another 2D array of the same size.

Answer 2

You are likely recalculating the same cell multiple times. For example, let's say you have a 3x3 grid where all cells are 1. You will calculate count(a, 1, 1) twice: once as part of count(a, 0, 1), and once as part of count(a, 1, 0).

You should instead keep track of those values you have calculated so far, and return those where available. For example:

static int count(int a[][], int i, int j) {
    return count(a, i, j, new int[a.length][a[0].length]);
}

static int count(int a[][], int i, int j, int[][] results) {
    if (results[i][j] != 0) {
        return results[i][j];
    }
    int rows = a.length;
    int cols = a[0].length;
    int ret;
    if(a[i][j] == 0)
        ret = 0;
    else if (i == rows - 1 && j == cols - 1)
        ret = a[i][j];
    else if (i == rows - 1)
        ret = a[i][j + 1];
    else if (j == cols - 1)
        ret = a[i + 1][j];
    else if (a[i][j] == 1)
        ret = count(a, i + 1, j, results) + count(a, i, j + 1, results);
    else
        ret = 0;
    results[i][j] = ret;
    return ret;
}