An Interest In:
Web News this Week
- April 26, 2024
- April 25, 2024
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
- April 20, 2024
LeetCode - Unique Paths
Problem statement
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Problem statement taken from: https://leetcode.com/problems/unique-paths
Example 1:
Input: m = 3, n = 7Output: 28
Example 2:
Input: m = 3, n = 2Output: 3Explanation:From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:1. Right -> Down -> Down2. Down -> Down -> Right3. Down -> Right -> Down
Example 3:
Input: m = 7, n = 3Output: 28
Example 4:
Input: m = 3, n = 3Output: 6
Constraints:
- 1 <= m, n <= 100- It's guaranteed that the answer will be less than or equal to 2 * 10^9
Explanation
Brute force approach
As per the problem statement the robot can move either down or right. We can use recursion to find the count. Let numberOfPaths(m, n) represent the counts of path to reach row number m and column number n in the grid. numberOfPaths(m, n) in C++ can be recursively written as following.
int numberOfPaths(int m, int n){ if (m == 1 || n == 1) return 1; return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);}
The time complexity of the above solution is exponential.
There are many overlapping sub-problems and hence we can use
dynamic programming approach to avoid re-computing
overlapping sub-problems.
Dynamic programming approach
We can avoid re-computing the overlapping sub-problems by constructing a temporary 2D array count[][] in bottom up manner using the above recursive approach.
int numberOfPaths(int m, int n){ // create a 2D array to store results of sub-problems int count[m][n]; // count of paths to reach any cell in first column is 1 for (int i = 0; i < m; i++) count[i][0] = 1; // count of paths to reach any cell in first row is 1 for (int j = 0; j < n; j++) count[0][j] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) count[i][j] = count[i - 1][j] + count[i][j - 1]; } return count[m - 1][n - 1];}
The time complexity of the above program is O(mn). The space complexity is O(mn). We can reduce the space more by O(n) where n is column size.
int numberOfPaths(int m, int n){ int count[n] = { 1 }; count[0] = 1; for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { count[j] += count[j - 1]; } } return count[n - 1];}
Combinatorics approach
We have to calculate m+n-2 C n-1 here which will be (m+n-2)! / (n-1)! (m-1)!
Let's check the algorithm on how to compute the above formula:
- set paths = 1- loop for i = n; i < m + n - 1; i++ - set paths = paths * i - update paths = paths / (i - n + 1)- return paths
C++ solution
class Solution {public: int uniquePaths(int m, int n) { long int paths = 1; for(int i = n; i < m + n - 1; i++){ paths *= i; paths /= (i - n + 1); } return int(paths); }};
Golang solution
func uniquePaths(m int, n int) int { paths := 1 for i := n; i < m + n - 1; i++{ paths *= i paths /= (i - n + 1) } return paths}
Javascript solution
var uniquePaths = function(m, n) { let paths = 1; for(let i = n; i < m + n - 1; i++){ paths *= i; paths /= (i - n + 1); } return paths;};
Let's dry-run our algorithm to see how the solution works.
Input: m = 3, n = 7Step 1: set paths = 1Step 2: loop for i = n; i < m + n - 1 i = 7 7 < 7 + 3 - 1 7 < 9 7 < 9 true paths = paths * i paths = 1 * 7 = 7 paths = paths / (i - n + 1) = 7 / (7 - 7 + 1) = 7 / 1 = 7 i++ i = 8Step 3: loop for i < m + n - 1 8 < 8 + 3 - 1 8 < 9 8 < 9 true paths = paths * i paths = 7 * 8 = 56 paths = paths / (i - n + 1) = 56 / (8 - 7 + 1) = 56 / 2 = 28 i++ i = 9Step 4: loop for i < m + n - 1 9 < 8 + 3 - 1 9 < 9 falseStep 5: return pathsSo we return answer as 28.
Original Link: https://dev.to/_alkesh26/leetcode-unique-paths-3mec
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To