Unique Paths Leetcode Solution
Unique Paths Leetcode Problem :
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m – 1][n – 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
Wildcard Matching Leetcode Problem Solution :
Constraints :
- 1 <= m, n <= 100
Example 1:
Input: m=3, n=2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Approach:
- Define a 2D array path of size m x n. This array will be used to store the number of unique paths to reach each cell in the grid.
- Initialize the first row and first column of the path array to 1. This is because there is only one way to reach any cell in the first row (by moving right) and only one way to reach any cell in the first column (by moving down).
- Iterate through the grid using two nested loops, starting from cell (1, 1) up to cell (m-1, n-1).
- For each cell (i, j), calculate the number of unique paths to reach it. This is done by summing the number of unique paths to reach the cell to the left (i, j-1) and the cell above (i-1, j). Since you can only move down or right, the number of unique paths to reach (i, j) is equal to the sum of the paths to (i, j-1) and (i-1, j).
- Continue this process until you have calculated the number of unique paths to reach the bottom-right corner of the grid, which is stored in path[m-1][n-1].
- Finally, return the value stored in path[m-1][n-1], which represents the number of unique paths to reach the destination.
Complexity:
Time complexity :
The provided code has a time complexity of O(m * n), where m and n are the dimensions of the grid.
Space complexity:
The space complexity of the code is O(m * n).
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int uniquePaths(int m, int n) {
long long int path[m][n];
long long int i,j;
for( i=0;i<m;i++){
for( j=0;j<n;j++){
if(i==0 || j==0) {
path[i][j] = 1;
}
else
path[i][j]=path[i][j-1]+path[i-1][j];
}
}
return path[m-1][n-1];
}
};class Solution {
public int uniquePaths(int m, int n) {
long[][] path = new long[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
path[i][j] = 1;
} else {
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
}
}
return (int) path[m - 1][n - 1];
}
}class Solution:
def uniquePaths(self, m: int, n: int) -> int:
path = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
path[i][j] = 1
else:
path[i][j] = path[i - 1][j] + path[i][j - 1]
return path[m - 1][n - 1]
Login/Signup to comment