A robot sits at the top-left corner of an m x n grid and can only move right or down. Return how many distinct paths it can take to reach the bottom-right corner.
Example
Input m = 3, n = 7
Output 28
Key Pointers
The number of ways to reach a cell equals the ways to reach the cell above it plus the ways to reach the cell to its left — those are the only two directions a path can arrive from.
The entire first row and first column have exactly 1 path each (a straight line), which seeds the whole table.
Only the previous row is ever needed to compute the next one, so the grid collapses to a single rolling array.
Step-by-Step Analysis
Start with a 1D array row of length n, all 1s (the first row of the grid).
For each subsequent grid row, build a new row where each cell is the cell to its left plus the value above it (from the previous row).
The first cell of every row stays 1, since there's only one way to stay against the left edge.
After processing all m rows, the last value in the final row is the answer.
Complexity
Time: O(m · n) — Space: O(n)
Code
def uniquePaths(m: int, n: int) -> int:
row = [1] * n
for _ in range(m - 1):
new_row = [1] * n
for c in range(1, n):
new_row[c] = new_row[c - 1] + row[c]
row = new_row
return row[-1]
Code Explanation
How the solution above works, piece by piece.
Every cell in the top row (and left column) can be reached in exactly one way: go straight.
Any other cell is entered from above or from the left: paths(r, c) = paths(r−1, c) + paths(r, c−1).
Only the previous row is needed, so row holds it and new_row is built left to right: new_row[c - 1] is the left neighbour, row[c] the one above.
After m − 1 new rows, row[-1] is the bottom-right count.
O(m × n) time, O(n) space.
Visual Walkthrough
Running it on m = 3, n = 7:
The robot can only move right or down, so the number of ways to reach a cell is the ways to reach the cell above plus the cell to its left. The first row and column have exactly 1 way. The code keeps only one row at a time.