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.
1int uniquePaths(int m, int n) {
2 int dp[m][n];
3 for (int i = 0; i < m; iThis C implementation uses a 2D array dp to keep track of the number of ways to reach each cell. After initializing the first row and column to 1, we iteratively compute the number of ways for other cells. The final result is stored in dp[m-1][n-1], which represents the bottom-right corner.
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
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.
This C code calculates the combinatorial value of picking (m-1) from (m+n-2) using an iterative approach to avoid overflow issues compared to factorial division directly.