Unique Paths
Problem Statement
A robot starts in the top-left corner of an m x n grid and wants to reach the bottom-right corner. The robot may move only down or right at any point. Return the number of distinct paths from start to finish.
Input
Two integers m and n, the grid dimensions.
Output
An integer: the number of valid paths from the top-left cell to the bottom-right cell.
Constraints
- •
1 <= m, n <= 100 - •
The answer is guaranteed to be less than or equal to **2 * 10^9**
Examples
Example 1
m = 3, n = 7
28Example 2
m = 3, n = 2
3Example 3
m = 1, n = 5
1Learning Objectives
- Define a grid DP state where each cell stores the number of ways to reach it.
- Derive the recurrence from the only two incoming neighbours: top and left.
- Seed the first row and first column correctly because edge cells have only one incoming direction.
- Compress a 2D grid table into a single 1D row array.
Intuition
Focus on the final step into a cell. Because the robot can only move down or right, any path that reaches cell (i, j) must have arrived from (i - 1, j) or (i, j - 1). Those two groups are disjoint because their final move is different.
That means every cell can be solved after its top and left neighbours are known. The first row and first column are special: there is only one straight-line way to reach any of those cells.
For space, notice that when scanning left to right, ways[j] still holds the value from the previous row, which is the top neighbour, while ways[j - 1] has already been updated for the current row, which is the left neighbour. Adding them gives the current cell.
Common mistakes
- ×Leaving the first row or first column as zero, which makes every later cell undercount.
- ×Thinking diagonal moves are allowed; the recurrence only uses top and left neighbours.
- ×Updating the 1D row from right to left, which would use stale left-neighbour values.
- ×Trying to enumerate paths explicitly instead of counting them with DP.
State Definition
Let dp[i][j] be the number of distinct paths from the top-left cell (0, 0) to cell (i, j). The answer is dp[m - 1][n - 1].
For the space-optimized version, let ways[j] be the current row value for column j after processing the current row.
State Transition
Base cases: dp[0][0] = 1, every cell in the first row is 1, and every cell in the first column is 1 because there is only one straight path along an edge.
For every inner cell:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
In the 1D row version, the same recurrence becomes ways[j] = ways[j] + ways[j - 1], where the old ways[j] is the top neighbour and ways[j - 1] is the left neighbour.
Solutions
Solution: Space-optimized row DP
Store only one row of path counts. Initialise the top row to all ones, then sweep each later row left to right so the current cell can reuse the top value and the already-updated left value.
Step-by-step
- Create an array ways of length n.
- Fill it with 1 because the top row has exactly one path to every column.
- For each later row, scan columns from 1 to n - 1.
- Add the left value ways[col - 1] into the top value ways[col].
- Return ways[n - 1], the number of paths to the bottom-right cell.
O(m · n)
O(n)
Every cell is processed once, and only the current row of counts is stored.
Java implementation
Dry Run
Sample input
m = 3, n = 4. Start with the top row already seeded as one path to every column.
| row | col | top value | left value | ways after update |
|---|---|---|---|---|
| top row | - | - | - | [1,1,1,1] |
| 1 | 1 | 1 | 1 | [1,2,1,1] |
| 1 | 2 | 1 | 2 | [1,2,3,1] |
| 1 | 3 | 1 | 3 | [1,2,3,4] |
| 2 | 1 | 2 | 1 | [1,3,3,4] |
| 2 | 2 | 3 | 3 | [1,3,6,4] |
| 2 | 3 | 4 | 6 | [1,3,6,10] |
The bottom-right value is 10, so a 3 x 4 grid has 10 unique paths. Each update combines the path count from above with the path count from the left.
Complexity Analysis
The 1D row compression keeps the same O(m · n) time as the full grid table while reducing memory from O(m · n) to O(n).
Space-optimized row DP
O(m · n)
O(n)
Every cell is processed once, and only the current row of counts is stored.
Interview Tips
Derive the recurrence from the last move into a cell. Once the interviewer sees top plus left, immediately mention that the first row and first column are all ones, then show the row-array optimization. If asked for a combinatorics shortcut, acknowledge it, but DP is the safer pattern for follow-ups with obstacles or costs.
Likely follow-ups
- How does the recurrence change when some cells are blocked by obstacles?
- How would you compute the minimum-cost path instead of the number of paths?
- Can you solve the same problem using combinations of down and right moves?
- What changes if the robot can also move diagonally?
Similar Problems
Key Takeaways
- Grid path counting often asks how many ways can reach this cell.
- When movement is only down and right, every inner cell receives paths from top and left.
- The first row and first column are base-case edges with exactly one path each.
- A row scan can compress the DP table to O(n) space.