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 <= 100
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's definition into a recursive function. The number of paths to a cell (r, c) is the sum of paths from the cell below (r+1, c) and the cell to the right (r, c+1). The recursion starts from (0, 0) and has a base case when it reaches the destination (m-1, n-1).
Algorithm
1. Define a recursive function countPaths(r, c)that returns the number of paths from cell(r, c) to the destination.
2. **Base Case 1:** If the robot goes out of bounds (r >= morc >= n), it's an invalid path. Return 0.
3. **Base Case 2:** If the robot reaches the destination (r == m - 1andc == n - 1), it has found one valid path. Return 1.
14. **Recursive Step:** For any other cell, the number of paths is the sum of paths from moving down and paths from moving right. Return
countPaths(r + 1, c) + countPaths(r, c + 1).
5. The initial call is countPaths(0, 0).
Walkthrough
We define a recursive function, say countPaths(r, c), which calculates the number of unique paths from the cell (r, c) to the destination (m-1, n-1). The function works as follows:
Base Cases:
If the robot reaches the destination (r == m-1 and c == n-1), it has found one valid path. So, we return 1.
If the robot goes out of the grid boundaries (r >= m or c >= n), it's an invalid path. So, we return 0.
Recursive Step:
For any other cell (r, c), the robot can either move down to (r+1, c) or right to (r, c+1).
The total number of paths from (r, c) is the sum of paths from these two subsequent cells: countPaths(r+1, c) + countPaths(r, c+1).
The initial call to the function will be countPaths(0, 0). This method suffers from a major drawback: it recomputes the number of paths for the same cells multiple times, leading to an exponential number of calls.
1public class Solution {2 public int uniquePaths(int m, int n) {3 return countPaths(0, 0, m, n);4 }56 private int countPaths(int r, int c, int m, int n) {7 // Base case: out of bounds8 if (r >= m || c >= n) {9 return 0;10 }11 // Base case: reached destination12 if (r == m - 1 && c == n - 1) {13 return 1;14 }15 // Recursive step16 return countPaths(r + 1, c, m, n) + countPaths(r, c + 1, m, n);17 }18}
Complexity
Time
O(2^(m+n))
Space
O(m + n)
Trade-offs
Pros
Simple to understand and implement.
Directly models the problem statement.
Cons
Extremely inefficient due to a massive number of redundant calculations (overlapping subproblems).
Will result in a 'Time Limit Exceeded' error for all but the smallest grid sizes.
This approach improves upon the brute-force recursion by storing the results of subproblems to avoid recomputation, a technique known as dynamic programming. We can use either a top-down (memoization) or a bottom-up (tabulation) approach. Both have the same time and space complexity, but the bottom-up approach is often slightly more efficient as it avoids recursion overhead.
Algorithm
1. Create a 2D array dpof sizem x n.
2. Initialize the first row (dp[0][j]) and the first column (dp[i][0]) with 1s, as there's only one way to reach these cells.
3. Iterate from i = 1tom-1andj = 1ton-1.
4. For each cell (i, j), calculate dp[i][j] = dp[i-1][j] + dp[i][j-1].
5. Return the value at dp[m-1][n-1].
Walkthrough
The number of ways to reach cell (i, j) is the sum of the ways to reach the cell above it, (i-1, j), and the cell to its left, (i, j-1). This gives us the recurrence relation: dp[i][j] = dp[i-1][j] + dp[i][j-1].
We use a bottom-up (tabulation) approach:
We create a 2D DP table dp[m][n].
dp[i][j] will store the number of unique paths to reach cell (i, j).
Initialization: Since the robot can only move right or down, all cells in the first row (dp[0][j]) and the first column (dp[i][0]) have only one way to be reached. So, we initialize dp[0][j] = 1 and dp[i][0] = 1 for all valid i and j.
Iteration: We then iterate through the rest of the grid, from (1, 1) to (m-1, n-1), and fill the table using the recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1].
The final answer is the value in the bottom-right cell, dp[m-1][n-1].
1public class Solution {2 public int uniquePaths(int m, int n) {3 int[][] dp = new int[m][n];45 // Initialize the first row and first column to 16 for (int i = 0; i < m; i++) {7 dp[i][0] = 1;8 }9 for (int j = 0; j < n; j++) {10 dp[0][j] = 1;11 }1213 // Fill the rest of the DP table14 for (int i = 1; i < m; i++) {15 for (int j = 1; j < n; j++) {16 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];17 }18 }1920 return dp[m - 1][n - 1];21 }22}
Complexity
Time
O(m * n)
Space
O(m * n)
Trade-offs
Pros
Much more efficient than brute-force.
Avoids recomputing subproblems, guaranteeing a solution within time limits for the given constraints.
Cons
Uses O(m*n) space, which can be substantial for large grids.
This approach optimizes the space complexity of the standard DP solution. When calculating the number of paths for the current row, we only need the values from the previous row. Therefore, we don't need to store the entire 2D DP table. We can use a 1D array to store the results of the previous row, reducing space complexity.
Algorithm
1. Create a 1D array dpof sizen(ormin(m, n) for optimization).
2. Initialize all elements of dp to 1.
3. Iterate from i = 1tom-1 (for rows).
4. Inside this loop, iterate from j = 1ton-1 (for columns).
5. Update dp[j] = dp[j] + dp[j-1].
6. After the loops, return dp[n-1].
Walkthrough
We observe that to compute the values for the current row i, we only need values from the previous row i-1. This allows us to reduce the space from a 2D array to a 1D array.
We use a 1D array dp of size n. This array will represent a row in the grid.
Initialization: We initialize the dp array with all 1s. This represents the first row of the grid, where there's only one way to reach each cell.
Iteration: We then loop for the remaining m-1 rows. In an inner loop, we iterate through the columns from j = 1 to n-1.
The update rule becomes dp[j] = dp[j] + dp[j-1]. Here, dp[j] on the right side represents the value from the previous row (dp[i-1][j]), and dp[j-1] represents the newly computed value from the current row's previous column (dp[i][j-1]).
After iterating through all the rows, the last element of the dp array, dp[n-1], will hold the final answer.
1public class Solution {2 public int uniquePaths(int m, int n) {3 int[] dp = new int[n];4 // Initialize the array with 1s5 for (int i = 0; i < n; i++) {6 dp[i] = 1;7 }89 // Iterate through the rows (starting from the second row)10 for (int i = 1; i < m; i++) {11 // Iterate through the columns (starting from the second column)12 for (int j = 1; j < n; j++) {13 // dp[j] holds the value from the previous row (paths from above)14 // dp[j-1] holds the value from the current row's previous column (paths from left)15 dp[j] = dp[j] + dp[j-1];16 }17 }1819 return dp[n - 1];20 }21}
Complexity
Time
O(m * n)
Space
O(n)
Trade-offs
Pros
Maintains the efficient O(m*n) time complexity.
Significantly reduces space complexity compared to the standard DP approach.
Cons
The logic can be slightly less intuitive to grasp than the 2D DP table approach.
This is the most efficient approach and involves looking at the problem from a mathematical perspective. Any path from the top-left to the bottom-right corner consists of a fixed number of 'down' moves and 'right' moves. The problem then becomes counting the number of unique sequences of these moves.
Algorithm
1. Calculate total moves N = m + n - 2.
2. Calculate moves of one type, say k = m - 1.
3. To optimize, choose the smaller of kandN-k. Let k = min(m-1, n-1).
4. Initialize result = 1 (using a long to prevent overflow).
5. Loop from i = 1tok. In each iteration, update result = result * (N - i + 1) / i.
6. Return the final result cast to an integer.
Walkthrough
To get from (0, 0) to (m-1, n-1), the robot must make a total of (m-1) moves down and (n-1) moves right.
The total number of moves is N = (m-1) + (n-1) = m + n - 2.
We need to choose K = (m-1) positions for the 'down' moves out of the N total moves (the rest will automatically be 'right' moves). This is a classic combination problem, and the number of ways is given by the binomial coefficient "N choose K", denoted as C(N, K).
The formula is C(N, K) = N! / (K! * (N-K)!).
In our case, N = m + n - 2 and K = m - 1. So the answer is C(m + n - 2, m - 1). Calculating factorials directly can lead to overflow. A better way is to compute the result iteratively using the property C(N, K) = (N * (N-1) * ... * (N-K+1)) / K!.
1public class Solution {2 public int uniquePaths(int m, int n) {3 // Total moves = (m-1) + (n-1) = m + n - 24 // We need to choose (m-1) down moves or (n-1) right moves.5 // This is C(m+n-2, m-1) or C(m+n-2, n-1)6 int N = m + n - 2;7 int k = m - 1; // or n - 189 long res = 1;10 // Calculate C(N, k) = (N * (N-1) * ... * (N-k+1)) / k!11 // To avoid large intermediate numbers, we do multiplication and division in each step.12 for (int i = 1; i <= k; i++) {13 res = res * (N - i + 1) / i;14 }15 return (int) res;16 }17}
Complexity
Time
O(min(m, n))
Space
O(1)
Trade-offs
Pros
Most efficient solution in terms of both time and space.
Elegant mathematical solution that avoids grid traversal.
Cons
Requires understanding of combinatorics.
Care must be taken with calculations to avoid integer overflow, although the iterative approach with long helps mitigate this.
Solutions
Solution
1class Solution {2public3 int uniquePaths(int m, int n) {4 int[] f = new int[n];5 Arrays.fill(f, 1);6 for (int i = 1; i < m; ++i) {7 for (int j = 1; j < n; ++j) {8 f[j] += f[j - 1];9 }10 }11 return f[n - 1];12 }13}
1/** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths =2 function (m, n) {3 const f = Array(n).fill(1);4 for (let i = 1; i < m; ++i) {5 for (let j = 1; j < n; ++j) {6 f[j] += f[j - 1];7 }8 }9 return f[n - 1];10 };
1class Solution {2public:3 int uniquePaths(int m, int n) {4 vector<int> f(n, 1);5 for (int i = 1; i < m; ++i) {6 for (int j = 1; j < n; ++j) {7 f[j] += f[j - 1];8 }9 }10 return f[n - 1];11 }12};
1class Solution:2 def uniquePaths(self, m: int, n: int) -> int: # avoid setting dp[][] to 1 for i==0 or j==0 as initialization dp = [[ 1 ] * n for _ in range ( m )] for i in range ( 1 , m ): for j in range ( 1 , n ): dp [ i ][ j ] = dp [ i - 1 ][ j ] + dp [ i ][ j - 1 ] return dp [ - 1 ][ - 1 ]
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
