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 * 109.
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2:
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
Constraints:
1 <= m, n <= 100The Unique Paths problem asks how many ways a robot can move from the top-left corner of an m x n grid to the bottom-right corner while only moving right or down. A common way to think about this is through Dynamic Programming. Each cell represents the number of ways to reach it, which is the sum of the paths from the cell above and the cell to the left. By building a DP table (or optimizing it to a single array), you can iteratively compute the number of paths to the destination.
Another elegant approach uses combinatorics. To reach the bottom-right cell, the robot must take exactly m-1 downward moves and n-1 rightward moves in any order. This becomes a combination problem where we calculate (m+n-2 choose m-1). The DP approach runs in O(m*n) time, while the combinatorial approach can achieve O(min(m,n)) time with constant space when computed carefully.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D Grid) | O(m * n) | O(m * n) |
| Dynamic Programming (1D Optimized) | O(m * n) | O(n) |
| Combinatorics (nCr) | O(min(m, n)) | O(1) |
take U forward
The key idea in this approach is to use a 2D table to store the number of ways to reach each cell. Initialize the first row and first column by 1 because there is only one way to reach any cell in the first row (all rights) and the first column (all downs). For the rest of the cells, the number of ways to reach that cell is the sum of the number of ways to reach the cell directly above it and the cell directly to the left of it.
Time Complexity: O(m * n) because each cell is computed once. Space Complexity: O(m * n) for the 2D DP array.
1var uniquePaths = function(m, n) {
2 let dp = Array(m).fill().map(() => Array(nJavaScript uses nested arrays to simulate the 2D table dp. After initializing base cases, it fills the table to compute each cell's path count, concluding in the bottom-right corner value.
A different method is to use combinatorics. The robot makes a total of (m + n - 2) moves, consisting of (m - 1) downward moves and (n - 1) rightward moves. The number of unique paths to organize these actions is the number of combinations of downs and rights: Combination(m+n-2, m-1) or Combination(m+n-2, n-1). This approach avoids the need for additional memory allocation for simple calculations.
Time Complexity: O(min(m, n)) for optimal comb calculations. Space Complexity: O(1).
1
long long combination(int n, int k) {
k = std::min(k, n - k);
long long result = 1;
for(int i = 1; i <= k; i++, n--) {
result = result * n / i;
}
return result;
}
int uniquePaths(int m, int n) {
return (int)combination(m + n - 2, m - 1);
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Unique Paths is a popular medium-level problem often used in technical interviews at large tech companies. It tests understanding of dynamic programming, combinatorics, and problem decomposition.
The optimal approach depends on constraints. Dynamic Programming is the most intuitive and builds the solution using subproblems in O(m*n) time. A more mathematical approach uses combinations to compute (m+n-2 choose m-1), which can reduce space usage to O(1).
A 2D or 1D array is commonly used for the Dynamic Programming solution. The array stores the number of ways to reach each cell based on previously computed values. With optimization, a single row array can store intermediate results.
Yes, the problem can also be solved using combinatorics. Since the robot must take a fixed number of right and down moves, the total number of paths is simply the number of ways to arrange those moves, which is calculated using combinations.
The C++ solution finds the combination of moves by optimally computing the value, minimizing integer range overflow while maintaining efficiency.