LeetMotion
There is a robot on an m × n grid at the top-left corner (grid[0][0]). The robot can only move right or down. Return the number of distinct paths to reach the bottom-right corner (grid[m-1][n-1]).
1 ≤ m, n ≤ 100At any cell (i, j), the robot came from either (i-1, j) (moved down) or (i, j-1) (moved right). There are no other options. So the number of ways to reach (i, j) is:
Base cases: any cell in the first row or first column has exactly 1 path (forced straight line). This recurrence means every cell only depends on its left and top neighbours — the hallmark of 2D DP.
The naive recursive approach recomputes the same cells exponentially many times. Memoization fixes that to O(m·n). Bottom-up DP fills the table iteratively. The space can be squeezed to O(n) since only the previous row is needed. Finally the math insight: every path is an arrangement of (m-1) downs and (n-1) rights, so the answer is C(m+n-2, n-1).
Explore every possible path via DFS. From cell (i,j), branch into dfs(i+1,j) and dfs(i,j+1). Return 1 when we hit the last row or column (only one direction left), 0 when out of bounds. Correct but exponential — the same subproblems are recomputed O(2^(m+n)) times.
def uniquePaths(self, m: int, n: int) -> int:
def dfs(i, j):
if i == (m - 1) or j == (n - 1):
return 1 # only one direction left
return dfs(i + 1, j) + dfs(i, j + 1)
return dfs(0, 0)Cache every dfs(i,j) result in a dictionary. On revisit, return the cached value instantly. Reduces exponential calls to exactly m·n unique subproblems — each computed once. Stack depth is at most m+n.
def uniquePaths(self, m: int, n: int) -> int:
dp = {}
def dfs(i, j):
if i == (m - 1) or j == (n - 1):
return 1
if (i, j) in dp:
return dp[(i, j)] # cache hit
dp[(i, j)] = dfs(i + 1, j) + dfs(i, j + 1)
return dp[(i, j)]
return dfs(0, 0)Fill an m×n table iteratively. Initialise every cell with 1 (base case: last row and last column each have only 1 path). Then fill from bottom-right to top-left: dp[i][j] = dp[i+1][j] + dp[i][j+1]. No recursion, no stack.
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(m - 2, -1, -1):
for j in range(n - 2, -1, -1):
dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
return dp[0][0]Since each row only reads from the row below, we can drop the full 2D table and keep just two 1D arrays: row (the row below, already computed) and newRow (being computed). After each outer loop, row = newRow.
def uniquePaths(self, m: int, n: int) -> int:
row = [1] * n # last row base case
for i in range(m - 1):
newRow = [1] * n # last col base case
for j in range(n - 2, -1, -1):
newRow[j] = newRow[j + 1] + row[j]
row = newRow
return row[0]We can eliminate newRow entirely by updating dp in-place from right to left. When we update dp[j], dp[j+1] already holds the new (right) value and dp[j] still holds the old (down) value — exactly what we need. This is the cleanest interview answer.
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for i in range(m - 1):
for j in range(n - 2, -1, -1):
dp[j] += dp[j + 1] # dp[j] (down) + dp[j+1] (right)
return dp[0]Every valid path makes exactly (m-1) down moves and (n-1) right moves — (m+n-2) moves total. The number of ways to arrange them is the binomial coefficient C(m+n-2, n-1). Computable in O(min(m,n)) with no DP at all.
from math import comb
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursion | O(2^(m+n)) | O(m+n) | Stack depth m+n, exponential overlap |
| Memoization | O(m·n) | O(m·n) | Each cell computed exactly once |
| Bottom-Up DP | O(m·n) | O(m·n) | Full table, no recursion overhead |
| Space Optimized | O(m·n) | O(n) | Two rows, clean to explain |
| Optimal 1D DP | O(m·n) | O(n) | In-place, interview favourite ✓ |
| Combinatorics | O(min(m,n)) | O(1) | C(m+n-2, n-1), no DP needed |
Recognise this pattern by three signals:
In the optimal 1D solution, we go j = n-2 down to 0. When we compute dp[j] += dp[j+1]:
dp[j+1] was just updated this row — it represents the right neighbour.dp[j] has not yet been updated this row — it represents the down neighbour (from the row below).Going left-to-right would corrupt the down value before we use it.
Every path from (0,0) to (m-1,n-1) is a sequence of m-1 D (down) moves and n-1 R (right) moves. These sequences are in bijection with ways to choose which n-1 of the m+n-2 positions are R — hence C(m+n-2, n-1). This collapses an O(m·n) DP to a single formula evaluation.
Going left-to-right in the optimal 1D solution overwrites the "down" value before it's read, producing wrong answers.
# WRONG — going left to right corrupts dp[j] before reading it as "down"
for j in range(1, n): # left → right
dp[j] += dp[j - 1]
# CORRECT — going right to left keeps dp[j] (down) intact
for j in range(n - 2, -1, -1):
dp[j] += dp[j + 1]The outer loop runs m-1 times (not m): the bottom row is already the base case. The inner loop goes down to index 0 but starts at n-2 (index n-1 stays 1, the base case).
Every cell in the last row and last column has exactly 1 path. If you initialise to 0 and forget to set the base, the entire grid will be 0.
m=1, n=1 → 1 (already there)m=1, n=5 → 1 (only one row, forced right)m=3, n=2 → 3m=3, n=3 → 6m=3, n=7 → 28
Discussion
…