Count All Number Of Paths Of A Given Matrix

Table of Contents

Introduction

This article will discuss a problem asked in interviews of product-based companies like Google and Adobe.

The problem statement we are given is as follows.

“Find the total number of paths for travelling from top-left to bottom-right of the M X N matrix with the constraint that you can either move Right or Down at each step. For example in a given point MATRIX[ i ] [ j ], you can move to either MATRIX[ i+1 ] [ j ] or MATRIX[ i ] [ j+1 ].”

Example Input-Output

Input: M=3, N=2
Output: 3
We are given a 3 x 2 matrix. To move from matrix[0][0] to matrix[2][1], we have the following possible paths.

Path 1 = (0, 0) -> (0, 1) -> (1, 1) -> (2, 1)
Path 2 = (0, 0) -> (1, 0) -> (2, 0) -> (2, 1)
Path 3 = (0, 0) -> (1, 0) -> (1, 1) -> (2, 1)
Hence a total of 3 paths are available, so the output is 3.

We would discuss the solution for this problem in detail, from the most intuitive approach to the most optimised approach.

Approach 1: Using Recursion

Recursion is the easiest and most obvious way to find the total number of paths to solve this problem. We will make function paths() that takes two parameters, ‘m’ and ‘n,’ and returns a single integer that is the number of paths.

Algorithm

As our base condition, we would check if our number of rows or columns is equal to 1.if either row or column is equal to 1, the given matrix is 1-D, and the number of paths would be equal to 1, i.e.,, only a single path is available.
If our base condition is not satisfied, we would call our recursive function, paths(), by providing it with a submatrix based on our move. If we move down in the matrix, the remaining submatrix would be of size M X N-1, and if we moved right, the remaining subarray would be of size M-1 X N. Hence we would return paths(m,n-1)+paths(m-1,n).

After all recursive calls, the function paths() would return the final answer, i.e., the total number of paths.

Code:

#include<bits/stdc++.h>
using namespace std;

int paths(int m,int n) {
    // Base condition.
    if(m == 1 || n == 1) {             
        return 1;
    }

    // Recursive call.
    return paths(m - 1, n) + paths(m, n - 1);  

}
 
int main()
{
    int m=5;
    int n=3;
    cout<<"Number of paths is: "<<paths(m,n);
}

Output:

Number of paths is: 15

Time Complexity: O(2^{(M + N)}), Where ‘M’ is the number of rows and ‘N’ is the number of matrix columns. Since for every recursive call, two more recursive calls are taking place. Thus the worst-case time complexity will be O(2^{(M + N)}).

Space Complexity:O(max(M, N)), where M is the number of rows and N is the number of matrix columns.Since due to the recursion stack space, the space complexity will be O(max(M, N)).

Approach-2: Using Memoization

The time complexity of the previous approach is exponential, which is very slow. The time complexity of the previous solution can be improved significantly by taking care of the overlapping subproblems.

Thus, in this approach, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.

Algorithm

We will make function paths() that takes two parameters, ‘m’ and ‘n,’ and returns a single integer of the number of paths.
We will make a 2-D table of size m*n and initialize it with -1;
We will create a helper function pathsHelper(), and along with ‘m’ and ‘n,’ we will also pass the 2D ‘lookupTable’.
As our base condition, we would check if our number of rows or columns is equal to 1.if either row or column is equal to 1, the given matrix is 1-D, and the number of paths would be equal to 1 i.e., only a single path is available.
Now we will check if the result of the current subproblem is already stored in the ‘lookupTable’ or not. If the result exists, we will return it.
Otherwise, we will call our recursive function pathsHelper() and store the returned value 6in ‘lookupTable’ and store in temp.
Finally, we will return ‘temp’ as our answer.

Code:

#include<bits/stdc++.h>
using namespace std;
int pathsHelper(int m, int n, vector<vector<int>> &lookupTable) {
    // Base condition.
    if(m == 1 || n == 1) {             
        return 1;
    }

    // Check for solved subproblems.
    if(lookupTable[m][n] != -1) {       
        return lookupTable[m][n];
    }

    // Recursive call.
    int temp = pathsHelper(m - 1, n, lookupTable) + pathsHelper(m, n - 1, lookupTable);  
    lookupTable[m][n] = temp;
    return temp;                     
}

int paths(int m, int n) {
    // Lookup table.
    vector<vector<int>>lookupTable(m + 1,vector<int>(n + 1,-1));           

    // Calling helper function.
    return pathsHelper(m,n,lookupTable);                             
}
 
int main()
{
    int m=5;
    int n=3;
    cout<<"Number of paths is: "<<paths(m,n);
}

Output:

Number of paths is: 15

Time Complexity: O(M * N), Where ‘M’ is the number of rows and ‘N’ is the number of matrix columns. Since the recursive approach will do the work in the order M * N. Thus the worst-case time complexity will be O(M * N)

Space Complexity: O(M * N), Where ‘M’ is the number of rows and ‘N’ is the number of matrix columns. Since the lookup table takes the space of M * N cells and thus the space complexity will be O(M * N).

Approach 3: Using Dynamic Programming

As we already know that we can improve our solution by taking care of the overlapping subproblems. Also, we can obtain the optimal solution of the problem by using the optimal solutions of its subproblems. The concept of Dynamic Programming can be applied here.

And we can avoid the recomputation of the same subproblems by storing the result in a temporary 2-D array dp as we did in the previous approach, but in this approach, we will use the bottom-up approach.

Algorithm

We will create the 2-D array dp of size M X N to store the result
We will initialize the first row and column of the dp array with 1 as we have only one path to reach the cell in the first row and column.
For filling the number of paths to reach a given cell, we know one thing that we can reach a given cell in two ways either by the cell just above it or by the cell just adjacent to its left so to fill that cell, we will sum the number of paths for both cells above it and adjacent to its left.
Finally, we will return the value of the last cell, which is ‘dp[m – 1][n – 1]’ as our final answer.

Code:

#include<bits/stdc++.h>
using namespace std;

int paths(int m,int n){
    // Reference table to store subproblems.
    int dp[m][n];                   

    // Paths to reach a cell in column 1.
    for (int i = 0; i < m; i++) {   
        dp[i][0] = 1; 
    }

    // Paths to reach a cell in row 1.
    for (int j = 0; j < n; j++) {   
        dp[0][j] = 1; 
    }       

    // Bottom up approach.
    for (int i = 1; i < m; i++) {   
        for (int j = 1; j < n; j++) { 
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
        }
    } 

    // Returning answer.
    return dp[m - 1][n - 1];        
}

int main()
{
    int m=5;
    int n=3;
    cout<<"Number of paths is: "<<paths(m,n);
}

Output:

Number of paths is: 15

Time Complexity: O(M * N), Where ‘M’ is the number of rows and ‘N’ is the number of columns of the matrix. Since we are running a nested loop M * N times, Thus the time complexity will be O(M * N).

Space Complexity: O(M * N), Where ‘M’ is the number of rows and ‘N’ is the number of matrix columns. Since we are storing elements in a 2-D Array, the total space taken will be of the order M * N. Thus, the space complexity will be O(M * N).

Approach 4:Space optimized Dynamic Programming

This approach is just the modification of the above dynamic programming approach to find the number of paths. In this approach, we would only use a 1-D array of size ‘n’, which is the number of rows in the matrix.

If you would take a closer look, you would notice that we are only using the matrix to get the number of paths to the cell just above it and the cell adjacent to its left, which can be done using a 1-D array.

Code:

#include<bits/stdc++.h>
using namespace std;
int paths(int m,int n){
    // Reference array to store subproblems.
    int dp[n] = {1};                   

    // Bottom up approach.
    dp[0] = 1;

    for (int i = 0; i < m; i++) {      
        for (int j = 1; j < n; j++) { 
            dp[j] += dp[j - 1];  
        }
    } 
    
    //Returning answer. 
    return dp[n - 1];                  
}
 
int main()
{
    int m=5;
    int n=3;
    cout<<"Number of paths is: "<<paths(m,n);
}

Output:

Number of paths is: 15

Space Complexity: O(N), Where ‘N’ is the number of columns of the matrix. Since we are storing elements in a 1-D Array, the total space taken will be of the order N. Thus, the space complexity will be O( N).

Approach 5: Using Combinatorics

If you take a closer look at the problem, you will notice that to reach the bottom right of the matrix, the number of steps we need to move to the right and the number of moves to down is fixed.

We need to move right N-1 times, and down M-1 times, so the total number of moves you need to make is M+N-2, and we need to arrange our N-1 right moves and M-1 down moves to get the total number of paths.

For example, let’s consider a 3 X 2 matrix.

We know that we need to take two right and one down. Possible arrangements are,

Right -> Right -> Down
Right -> Down -> Right
Down -> Right -> Right

The total number of possible ways are three. We can derive this result by using the combination. As we discussed above we need to make a total of M+N-2 moves in which N-1 moves are right to move so to get the total number of paths we need to choose N-1 places out of M+N-2 places so,

Total number of paths= ^M+N-2C_N-1

We can simplify this statement as (M+N-2)*(M+N-3)*…….N/(M-1)!

So for 3×2 matrix total number of paths =³C₂

=3!/2!*1!

Code:

#include<bits/stdc++.h>
using namespace std;

int paths(int m, int n)
{
    // We have to calculate m+n-2 C n-1 
    // which will be (m+n-2)! / (n-1)! (m-1)!
    int res = 1;
    for (int i = n; i < (m + n - 1); i++) {
        res *= i;
        res /= (i - n + 1);
    }
    return res;
}
 
int main()
{
    int m=5;
    int n=3;
    cout<<"Number of paths is: "<<paths(m,n);
}

Output:

Number of paths is: 15

Time complexity: O(M-1) as we are running a loop from M+N-1 till n.
Space complexity: O(1)

Key Takeaways

This article discussed a very engaging and interesting problem to find the total number of paths to reach the bottom right of the given matrix. This problem has been very frequently asked about in google and other product-based companies. The article discussed every approach to solve this problem, from the most basic to the most optimized solution.

If you want to solve more problems like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at CodeStudio.

Happy Learning!

By Pranchal Agrahari