Frontend Beauty
ESC

Type to search the knowledge base.

Unique Paths

Robot on m×n grid moves only right/down — DP grid or combinatorial C(m+n-2, m-1).

intermediate3 min read
  • dsa
  • dp
  • interview
  • Google
  • Meta

The problem

Robot at top-left of m × n grid. Can only move right or down. How many unique paths to bottom-right?

Input:  m = 3, n = 7
Output: 28

Input:  m = 3, n = 2
Output: 3
// DDR, DRD, RDD

Brute force: recursion

function uniquePathsBrute(m: number, n: number): number {
  function dfs(r: number, c: number): number {
    if (r === m - 1 && c === n - 1) return 1;
    if (r >= m || c >= n) return 0;
    return dfs(r + 1, c) + dfs(r, c + 1);
  }
  return dfs(0, 0);
}

Exponential without memo.

Optimal DP

dp[r][c] = dp[r-1][c] + dp[r][c-1], first row/col = 1.

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({ length: m }, () => Array(n).fill(1));
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }
  return dp[m - 1][n - 1];
}

Space-optimized to one row:

function uniquePaths1D(m: number, n: number): number {
  const dp = Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[c] += dp[c - 1];
    }
  }
  return dp[n - 1];
}

Combinatorics

Need exactly (m-1) downs and (n-1) rights — total steps m+n-2. Choose positions for downs: C(m+n-2, m-1).

function uniquePathsComb(m: number, n: number): number {
  const N = m + n - 2;
  const K = Math.min(m - 1, n - 1);
  let res = 1;
  for (let i = 1; i <= K; i++) {
    res = (res * (N - K + i)) / i;
  }
  return Math.round(res); // guard float noise in JS
}
Time O(m·n) DP / O(min(m,n)) comb
Space O(m·n) or O(n)

Edge cases

  • m = 1 or n = 1 → 1
  • Large grids — comb needs careful multiply order to stay exact
  • Obstacles variant → Unique Paths II

Common bugs

  • Initializing dp with 0 instead of 1 on borders
  • Off-by-one in dimensions
  • Integer division order in comb formula

Interview delivery

  1. Recurrence from left/up.
  2. DP table or 1D.
  3. Optional binomial.
  4. O(mn).
  5. Mention obstacles follow-up.

DP table for 3×3

1 1 1
1 2 3
1 3 6

Answer 6. Each cell sum of top and left.

Combinatorial identity

Paths = sequences of (m-1) D and (n-1) R. Number = (m+n-2)! / ((m-1)!(n-1)!). Compute multiplicatively to keep intermediate values smaller.

Unique Paths II

Add obstacles: dp[r][c]=0 if rock; skip contributing from blocked neighbors. Same recurrence, extra guard.

Further reading