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 <= 100Problem Overview: You are given an m x n grid. Starting at the top-left cell, you can only move either right or down. The task is to count how many distinct paths lead to the bottom-right cell.
Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)
The grid naturally forms overlapping subproblems. Any cell (i, j) can only be reached from the cell above (i-1, j) or from the left (i, j-1). That means the number of ways to reach a cell equals the sum of those two previous states. Build a 2D DP table where dp[i][j] = dp[i-1][j] + dp[i][j-1]. Initialize the first row and first column with 1 because there is only one way to move straight right or straight down. Iterate through the grid row by row and fill the table. The final answer sits at dp[m-1][n-1]. This method is easy to reason about and commonly used when learning dynamic programming patterns.
The DP solution can also be optimized to O(n) space by storing only one row. Each position accumulates paths from the left and the current value representing the path from above. The transition logic stays the same but memory drops significantly.
Approach 2: Combinatorial Approach (O(min(m,n)) time, O(1) space)
Reframe the grid as a sequence of moves instead of positions. To reach the bottom-right corner, you must make exactly (m-1) downward moves and (n-1) right moves. The total path length is therefore (m+n-2). The problem becomes choosing where the downward moves appear in that sequence. Mathematically, the number of unique paths equals the binomial coefficient C(m+n-2, m-1) or C(m+n-2, n-1). Compute this efficiently by multiplying and dividing iteratively to avoid factorial overflow. This technique relies on basic math and combinatorics principles.
The combinatorial solution runs in linear time relative to the smaller dimension and uses constant memory. It avoids building a grid entirely and directly computes the number of arrangements of moves.
Recommended for interviews: The dynamic programming approach is the most commonly expected explanation because it demonstrates understanding of state transitions and grid DP patterns. After presenting DP, strong candidates often point out the combinatorial observation as a mathematical optimization. Showing both proves you understand the structure of the problem and can move from brute reasoning to an optimal formula.
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.
This 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) because each cell is computed once. Space Complexity: O(m * n) for the 2D DP array.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(min(m, n)) for optimal comb calculations. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n) because each cell is computed once. Space Complexity: O(m * n) for the 2D DP array. |
| Combinatorial Approach | Time Complexity: O(min(m, n)) for optimal comb calculations. Space Complexity: O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (2D Grid) | O(m*n) | O(m*n) | Best for understanding grid DP transitions and when clarity matters more than memory. |
| Dynamic Programming (1D Optimization) | O(m*n) | O(n) | When grid dimensions are large and you want the standard DP approach with reduced memory. |
| Combinatorial Formula | O(min(m,n)) | O(1) | Optimal mathematical solution when you recognize the problem as counting permutations of moves. |
DP 8. Grid Unique Paths | Learn Everything about DP on Grids | ALL TECHNIQUES 🔥 • take U forward • 419,377 views views
Watch 9 more video solutions →Practice Unique Paths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor