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 a 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);
}
You can also try this code with Online C++ Compiler
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).
Read More - Time Complexity of Sorting Algorithms
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);
}
You can also try this code with Online C++ Compiler
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);
}
You can also try this code with Online C++ Compiler
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(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).
Check out Longest Common Substring
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 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-2CN-1
We can simplify this statement as (M+N-2)*(M+N-3)*.......N/(M-1)!
So for 3x2 matrix total number of paths =3C2
=3!/2!*1!
=3
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);
}
You can also try this code with Online C++ Compiler
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)
Must Read - Strong number in c
Conclusion
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 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 Code Studio.
Happy Learning!
34+ registered 
