Number of Paths In a Matrix Problem

Consider a maze mapped to a matrix with the upper left corner at coordinates (row, column) = (0, 0). You can only move towards the right or down from a cell. Determine the number of distinct paths through the maze. You must always start from the top-left position (0, 0) and end at the bottom-right (n-1, m-1).

For example, consider the following diagram where “1” indicates an open cell and “0” indicates a blocked cell. You can only travel through open cells, so no path can go through the cell (0, 2).

There are two possible paths from cell (0, 0) to cell (1, 3) in this matrix. Complete the function numberOfPaths, such that function returns the number of paths through the matrix, modulo (10^9 + 7).

Here are a couple of examples to get you started:

Example One

Input:
3
4
1 1 1 1
1 1 1 1
1 1 1 1

Output: 10

There are 10 possible paths from cell (0, 0) to cell (2, 3).

Example Two

Input:
2
2
1 1
0 1

Output: 1

There is one possible path from cell (0, 0) to cell (1, 1).

Notes:

Input Parameters: The function contains a single argument — a two-dimensional integer array called “matrix.”

Output: Return an integer — the number of possible paths from (0, 0) to (n-1, m-1).

Constraints:

• 1 <= n*m <= 2*10^6
• Each cell, matrix[i][j], contains 1, indicating it is accessible, or 0, indicating it is not accessible, where 0<=i<n and 0<=j<m

‍Solution 1: Brute Force (brute_force_solution.java)

We have a matrix with n rows and m columns, where each cell, matrix[A][B], denotes whether it is accessible or not.

We will use recursion to solve this problem.

We know that the number of ways to reach a cell is the sum of the number of ways to reach the cell to its left and the number of ways to reach the cell above it. Therefore:

No. of ways to reach matrix[i][j] =
No. of ways to reach matrix[i-1][j] + No. of ways to reach matrix[i][j-1]

This is because we can only go right or downward from any cell.

Now, we start from a cell and perform recursion to find the number of ways to reach cell (n-1, m-1): 

recur(matrix, n-1, m-1) = recur(matrix, n-2, m-1) + recur(matrix, n-1, m-2)

For each cell, we will check if it is accessible or not. If it is not, we simply return 0, as there is no way to reach it. The base condition would be that if cell (0,0) is accessible, then the number of ways to reach it is 1.

Time Complexity:

O(2^(rows+columns))

In each recursion step, we will either reduce n by 1 or m by 1. Hence, the recurrence relation will be:

T(n + m) = T(n – 1 + m) + T(n + m – 1) + O(1)

T(n + m) = 2 * T(n – 1 + m) + O(1)

Therefore, it is O(2^(n+m)).

Auxiliary Space Used:

O(rows+columns)

We do not create any auxiliary array for the solution. We use recursion, which uses O(rows+columns) stack space as the maximum steps can be rows+columns at a time.

Space Complexity:

O(rows*columns)

Input takes O(rows*columns) space, the auxiliary space used is O(rows+columns), and the output takes O(1). Summing these up, we get O(rows*columns).

// -------- START --------
    public static int numberOfPaths(List<list> matrix){
        int n = matrix.size(), m = matrix.get(0).size(), MOD = 1000000007;
        int ans = recur(matrix, n-1, m-1, MOD);
        return ans;
    }
    
    public static int recur(List<list> matrix, int n, int m, int MOD) {
        int ans = 0;
        //stopping condition
        if(n<0 0="" 1="" ||="" m<0)="" {=""  =""  return="" 0;=""  }="" if="" a="" cell="" is="" restricted,="" there="" are="" ways="" to="" reach="" there.=""  if(matrix.get(n).get(m)="=0)" base="" condition:="" (0,0)="" accessible,="" we="" have="" way="" it.=""  if(n="=0" &&="" m="=0)" 1;="" *number="" of=""  a[i][j]="number" a[i-1][j]="" +="" number="" a[i][j-1]*=""  ans="" n-1,="" m,="" mod)="" recur(matrix,="" n,="" m-1,="" mod))%mod;="" ans;="" --------="" end="" <="" code=""></list</list

Solution 2: Optimal Solution Using Dynamic Programming (optimal_solution.java)

We have a matrix with n rows and m columns, where each cell, matrix[A][B], denotes whether it is accessible or not.

Solution 1 (recursive) was exponential. We are visiting multiple states over and over, and then recursing for them, which we can surely avoid. To avoid revisiting states that have already been visited, we can store them in a dp array, so that they can be accessed as and when needed. This approach is known as Dynamic Programming.

Here’s how we do it:

1. We know that for any cell (i, j), the number of paths to reach it would be the number of paths to reach cell (i-1, j) + the number of paths to reach cell (i, j-1).
2. For any accessible cell matrix[i][j], we maintain the count of number of paths to reach this cell in a separate two-dimensional array dp[i][j], where dp[i][j] = dp[i-1][j] + dp[i][j-1], given that cell (i, j) is accessible.
3. We return the value of dp[i][j] as the answer.

Time Complexity:

O(n*m), considering the number of rows is n and columns is m.

We traverse the entire array matrix once and simultaneously traverse the dp array to keep the number of ways to reach that cell from cell (0,0). So, we travel both arrays at most once, and hence, the time complexity is O(n*m).

Auxiliary Space Used:

O(n*m), considering the number of rows is n and columns is m.

We create a two-dimensional array dp of size n*m to store the number of paths from cell (0,0) to the current cell. Hence, the auxiliary space used is O(n*m).

Space Complexity:

O(n*m), considering the number of rows is n and columns is m.

Input complexity is O(n*m), auxiliary space used is O(n*m), and output space complexity is O(1). Hence, total complexity will be O(n*m).

// -------- START --------
    public static int numberOfPaths(List<list> matrix){
        int n = matrix.size(), m = matrix.get(0).size(), MOD = 1000000007;
        if(matrix.get(0).get(0)== 0 || matrix.get(n-1).get(m-1)==0) {
            return 0;
        }
        int[][] dp = new int[n][m];
        //if cell (0,0) is accessible, number of ways to reach it is 1
        dp[0][0] = 1;
        //filling for the cells in first row.
        for(int i = 1; i < m ;i++){
            if(matrix.get(0).get(i)==1 && dp[0][i-1] == 1){
                dp[0][i] = 1;
            }
        }
        //filling for the cells in the first column
        for(int i = 1; i < n ;i++){
            if(matrix.get(i).get(0)==1 && dp[i-1][0] == 1){
                dp[i][0] = 1;
            }
        }
        /*number of ways to reach 
        cell(i,j) = number of ways to reach cell(i-1,j) + number of ways to reach cell (i,j-1)*/
        for(int i = 1; i < n; i++){
            for(int j = 1; j<m; j++){    if(matrix.get(i).get(j)="=1){"  dp[i][j]="(dp[i-1][j]" + dp[i][j-1])%mod;  }  return dp[n-1][m-1]; -------- end < code></m;></list