2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ @Vogel612, I updated my post now, actually the issue is with performance now, the test cases are fine now. \$\endgroup\$ – learner Feb 27 '18 at 22:32
  • \$\begingroup\$ You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary #include lines, and a main() that shows how to call your function (you should probably include your test cases there). It can really help reviewers if they are able to compile and run your program. \$\endgroup\$ – Toby Speight Feb 28 '18 at 8:08
1
\$\begingroup\$

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 , 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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

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.