Problem Statement: Given a matrix m X n, count paths from left-top to the right bottom of a matrix with the constraints that from each cell you can either only move to the rightward direction or the downward direction.
Example 1:
Input Format: m = 2, n= 2 Output: 2
Explanation: From the top left corner there are total 2 ways to reach the bottom right corner:
Step 1: Right ->> Down
Step 2: Down ->> Right
Example 2:
Input Format: m = 2, n= 3 Ouput: 3
Explanation: From the top left corner there is a total of 3 ways to reach the bottom right corner.
Step 1: Right ->> Right ->> Down
Step 2: Right ->> Down ->> Right
Step 3: Down ->> Right->> Right
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach: The problem states that we can either move rightward or downward direction. So we recursively try out all the possible combinations.
- At first, we are at the (0,0) index let’s assume this state as (i,j). From here we can move towards the bottom as well as towards the right and we recursively move until we hit the base case.
2. At any point of time when the recursive call goes out of the matrix boundary (example: let’s assume m = 2, n= 2, and the current position of i and j is (2,0) which is out of matrix boundary), we’ll return zero because from here there are no possible paths beyond and that is the first base case.
3. Whenever the recursive call reaches the end we’ll return 1 because we have found one possible path to reach the end.
4. In the recursive tree what result we have got from the left transition and the right transition will sum it up and return the answer.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int countPaths(int i,int j,int n,int m)
{
if(i==(n-1)&&j==(m-1)) return 1;
if(i>=n||j>=m) return 0;
else return countPaths(i+1,j,n,m)+countPaths(i,j+1,n,m);
}
int uniquePaths(int m, int n) {
return countPaths(0,0,m,n);
}
};
int main()
{
Solution obj;
int totalCount= obj.uniquePaths(3,7);
cout<<"The total number of Unique Paths are "<<totalCount<<endl;
}Output:
The total number of Unique Paths are 28
Time Complexity: The time comp[lexity of this recursive solution is exponential.
Space Complexity: As we are using stack space for recursion so the space complexity will also be exponential.
Python Code
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
def countPaths(i, j, n, m):
if i == (n - 1) and j == (m - 1):
return 1
if i >= n or j >= m:
return 0
else:
return countPaths(i + 1, j, n, m) + countPaths(i, j + 1, n, m)
return countPaths(0, 0, m, n)
if __name__ == "__main__":
obj = Solution()
totalCount = obj.uniquePaths(3, 7)
print("The total number of Unique Paths are ", totalCount)Output:
The total number of Unique Paths are 28
Time Complexity: The time comp[lexity of this recursive solution is exponential.
Space Complexity: As we are using stack space for recursion so the space complexity will also be exponential.
Solution 2: Dynamic Programming Solution
Intuition: The dynamic programming solution of this problem is a bit extension of the recursive solution. In recursive solutions, there are many overlapping subproblems. In this solution instead of traversing all the possible paths, whenever we get the result we’ll store it in a matrix for future use. Whenever we encounter the same subproblem we directly get the value from the matrix instead of recomputing it. By this memorization technique, we can avoid the recomputation and the time complexity will be drastically reduced. This is the main intuition behind this dynamic programming solution.
Approach:
Step 1: Take a dummy matrix A[ ][ ] of size m X n and fill it with -1.
Step 2: At first, we are at the (0,0) index let’s assume this state as (i,j). From here we can move towards the bottom as well as towards the right and we recursively move until we hit the base case.
Step 3: At any point of time when the recursive call goes out of the boundary (example: let’s assume m = 2, n= 3, and the current position of i and j is (2,0) which is out of matrix boundary), we will return zero because from here there are no possible paths beyond and that is the first base case.
Step 4: Whenever the recursive call reaches the end we’ll return 1 because we have found one possible path to reach the end.
Step 5: The only change in the dynamic programming solution is whenever we are returning answers we store them in the matrix A[i][j] and wherever we are making a recursive call we simply check if that state is already visited or not in other words we’ll check if A[i][j] is -1 or not if it is not -1 that means that there is a subproblem which is repeating. Now instead of recomputing the subproblem, we’ll return the value at A[i][j].
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int countPaths(int i,int j,int n,int m,vector<vector<int>> &dp)
{
if(i==(n-1)&&j==(m-1)) return 1;
if(i>=n||j>=m) return 0;
if(dp[i][j]!=-1) return dp[i][j];
else return dp[i][j]=countPaths(i+1,j,n,m,dp)+countPaths(i,j+1,n,m,dp);
}
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
//dp[1][1]=1;
int num=countPaths(0,0,m,n,dp);
if(m==1&&n==1)
return num;
return dp[0][0];
}
};
int main()
{
Solution obj;
int totalCount= obj.uniquePaths(3,7);
cout<<"The total number of Unique Paths are "<<totalCount<<endl;
}Output:
The total number of Unique Paths are 28
Time Complexity: The time complexity of this solution will be O(n*m) because at max there can be n*m number of states.
Space Complexity: As we are using extra space for the dummy matrix the space complexity will also be O(n*m).
Python Code
from typing import List
class Solution:
def countPaths(self, i: int, j: int, n: int, m: int, dp: List[List[int]]) -> int:
if i == (n - 1) and j == (m - 1):
return 1
if i >= n or j >= m:
return 0
if dp[i][j] != -1:
return dp[i][j]
else:
dp[i][j] = self.countPaths(
i + 1, j, n, m, dp) + self.countPaths(i, j + 1, n, m, dp)
return dp[i][j]
def uniquePaths(self, m: int, n: int) -> int:
dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
# dp[1][1]=1;
num = self.countPaths(0, 0, m, n, dp)
if m == 1 and n == 1:
return num
return dp[0][0]
if __name__ == "__main__":
obj = Solution()
totalCount = obj.uniquePaths(3, 7)
print("The total number of Unique Paths are", totalCount)Output:
The total number of Unique Paths are 28
Time Complexity: The time complexity of this solution will be O(n*m) because at max there can be n*m number of states.
Space Complexity: As we are using extra space for the dummy matrix the space complexity will also be O(n*m).
Solution 3: Combinatorics Solution
Intuition: If we observe examples there is a similarity in paths from start to end. Each time we are taking an exactly m+n-2 number of steps to reach the end.
From start to reach the end we need a certain number of rightward directions and a certain number of downward directions. So we can figure out we need n-1 no. of rightward direction and m-1 no. of downward direction to reach the endpoint.
Since we need an m+n-2 number of steps to reach the end among those steps if we choose n-1 rightward direction or m-1 downward direction and calculate the combinations ( ie: m+n-2Cn-1 or m+n-2Cm-1) we’ll get the total number of paths.
Approach: The approach of this solution is very simple just use a for loop to calculate the m+n-2Cn-1 or m+n-2Cm-1
Dry Run: We’ll take the input m = 2 and n = 3
According to our observation, we need an m+n-2 number of steps to reach the end. So we need 3 steps and in every step, we need an n-1 number of rightward direction and m-1 number of downward direction. Among 3 steps if we choose 2 rightward directions then the result will be 3 ( 3C2) or among 3 steps if we choose 1 downward direction then the result will also be 3 ( 3C1).
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int uniquePaths(int m, int n) {
int N = n + m - 2;
int r = m - 1;
double res = 1;
for (int i = 1; i <= r; i++)
res = res * (N - r + i) / i;
return (int)res;
}
};
int main()
{
Solution obj;
int totalCount= obj.uniquePaths(2,3);
cout<<"The total number of Unique Paths are "<<totalCount<<endl;
}Output:
The total number of Unique Paths are 3
Time Complexity: The time complexity of this solution will be O(n-1) or O(m-1) depending on the formula we are using.
Space Complexity: As we are not using any extra space the space complexity of the solution will be O(1).
Python Code
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
N = n + m - 2
r = m - 1
res = 1
for i in range(1, r + 1):
res = res * (N - r + i) / i
return int(res)
if __name__ == "__main__":
obj = Solution()
totalCount = obj.uniquePaths(2, 3)
print("The total number of Unique Paths are", totalCount)Output:
The total number of Unique Paths are 3
Time Complexity: The time complexity of this solution will be O(n-1) or O(m-1) depending on the formula we are using.
Space Complexity: As we are not using any extra space the space complexity of the solution will be O(1).
Special thanks to Soumik Dutta and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article