62. Unique Paths

A robot on an m×n grid can only move right or down — count every distinct route to the bottom-right corner using a simple 2D DP recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1], or solve it in O(1) space with a rolling row, or even in O(1) time via the combinatorial formula C(m+n-2, m-1).

● Medium2D DPCombinatoricsTypeScript

PROBLEM What we're solving

A robot starts at the top-left of an m × n grid and must reach the bottom-right. It can only move right or down at each step. How many distinct paths are there?

Concrete example: m=3, n=7 → 28 paths. With m=3, n=3 → 6 paths. You can trace them in the Visualize tab.

KEY IDEA Every cell is reachable from exactly two directions

Insight → to arrive at dp[i][j] you must have come from dp[i-1][j] (above) or dp[i][j-1] (left) — never both at once. So the number of paths to (i, j) is exactly the sum of paths to those two neighbors: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base case: every cell in the top row and left column has exactly 1 path.

RECURRENCE Build the DP table

0 · Allocate. Create an m × n table filled with 1. This seeds the top row and left column in one shot — those edge cells truly have only one path.
1 · Fill interior. For i from 1 to m-1, for j from 1 to n-1: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Each cell only needs its left and top neighbors, which are already computed.
2 · Return. dp[m-1][n-1] holds the answer.

Classic confusion → people forget that the first row and column must be initialized to 1, not 0. Using fill(0) and trying to handle the base case inside the loop leads to index-out-of-bounds or an answer of 0. The cleanest fix: just fill(1) upfront and start both loops at index 1.

COST Complexity & space reduction

Full 2D table

O(m·n)

O(m·n) time and O(m·n) space.

Rolling single row

O(m·n) / O(n)

Same time; only O(n) space needed.

Rolling row

Because dp[i][j] only needs row i-1 and the current row up to j-1, you only need to keep one row in memory. Overwrite in place: row[j] += row[j-1] — at that moment row[j]still holds the old "from above" value and row[j-1]was just updated to "from left".

Combinatorial closed form

The robot always takes exactly m-1 down-steps and n-1 right-steps, for m+n-2 total moves. The path count equals the number of ways to choose which m-1 of them are "down": C(m+n-2, m-1). For m=3, n=7: C(8, 2) = 28. This runs in O(min(m,n)) time and O(1) space.

Pattern transfer → this exact recurrence (sum of two predecessors) powers Unique Paths II (add obstacle check before writing), Minimum Path Sum (replace + with min then add current cost), Pascal's Triangle(the dp table itself is Pascal's triangle offset by one), and any 2D DP on a directed grid.

RUN IT Fill the DP grid row by row

rows (m)cols (n)

step 0 / 34

STARTStarting a 3×7 DP table. Seed the entire top row and left column to 1 — there is exactly one way to reach any cell on the edge (go straight).

1function uniquePaths(m: number, n: number): number {
2  // dp[i][j] = number of unique paths to reach row i, col j
3▶  const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1));
4 
5  // Top row and left column are already seeded to 1 (fill(1) above).
6  // Only one way to reach any edge cell: go straight.
7 
8  for (let i = 1; i < m; i++) {
9    for (let j = 1; j < n; j++) {
10      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
11    }
12  }
13 
14  return dp[m - 1][n - 1];
15}
16 
17// O(1)-space rolling optimisation: one row is enough.
18function uniquePathsO1(m: number, n: number): number {
19  let row = Array(n).fill(1);
20  for (let i = 1; i < m; i++) {
21    for (let j = 1; j < n; j++) {
22      row[j] += row[j - 1]; // row[j] holds "from above"; row[j-1] just became "from left"
23    }
24  }
25  return row[n - 1];
26}
27 
28// Combinatorial closed form: C(m+n-2, m-1)
29function uniquePathsMath(m: number, n: number): number {
30  // Robot takes exactly (m-1) down-steps and (n-1) right-steps = m+n-2 total.
31  // Choose which m-1 of them are down-steps.
32  const total = m + n - 2;
33  const choose = m - 1;
34  let result = 1;
35  for (let i = 0; i < choose; i++) {
36    result = (result * (total - i)) / (i + 1);
37  }
38  return Math.round(result);
39}

j=0

j=1

j=2

j=3

j=4

j=5

j=6

i=0

i=1

i=2

current cellsource cellsanswer cell

slowfast

TYPESCRIPT The solution, annotated

uniquePaths.ts
function uniquePaths(m: number, n: number): number {
  // dp[i][j] = number of unique paths to reach row i, col j
  const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1));

  // Top row and left column are already seeded to 1 (fill(1) above).
  // Only one way to reach any edge cell: go straight.

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
}

// O(1)-space rolling optimisation: one row is enough.
function uniquePathsO1(m: number, n: number): number {
  let row = Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1]; // row[j] holds "from above"; row[j-1] just became "from left"
    }
  }
  return row[n - 1];
}

// Combinatorial closed form: C(m+n-2, m-1)
function uniquePathsMath(m: number, n: number): number {
  // Robot takes exactly (m-1) down-steps and (n-1) right-steps = m+n-2 total.
  // Choose which m-1 of them are down-steps.
  const total = m + n - 2;
  const choose = m - 1;
  let result = 1;
  for (let i = 0; i < choose; i++) {
    result = (result * (total - i)) / (i + 1);
  }
  return Math.round(result);
}

Reading it block by block

Line 3 — allocate and seed. Array.from({ length: m }, () => Array(n).fill(1)) creates the full grid pre-filled with 1. This implicitly handles the base case: every cell on the top row (i=0) and left column (j=0) correctly holds 1 because there is exactly one path along the edge.

Lines 9–13 — fill interior cells. Both loops start at index 1 to skip the already-correct border. The recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] is safe because both sources are in earlier rows or earlier columns — guaranteed computed.

Lines 19–25 — O(1)-space rolling row. Keep only one row. Before updating row[j], its current value is the "from above" contribution (carried from the previous outer-loop iteration). After row[j-1] is updated it holds "from left". So row[j] += row[j-1] is exactly the 2D recurrence collapsed to 1D.

Lines 28–37 — combinatorial formula. The robot's journey is always m+n-2 steps; we choose m-1of them to be "down". That is C(m+n-2, m-1). The loop computes the binomial coefficient in O(k) via the multiplicative formula to avoid factorial overflow.

Complexity → 2D DP: O(m·n) time, O(m·n) space. Rolling row: same time, O(n) space. Combinatorial: O(min(m,n)) time, O(1) space — the asymptotically best, but the DP version is what interviewers want you to explain first.

INTERVIEWFollow-ups they'll ask

"Can you reduce the space?" Yes — a single rolling row cuts space to O(n). Walk through row[j] += row[j-1] and explain why the overwrite is safe.
"Unique Paths II — what changes with obstacles?" Before writing a cell check if it is blocked; if so, set it to 0 (no path reaches it). The recurrence is otherwise identical.
"Minimum Path Sum — what changes?" Replace the + with minand add the current cell's cost: dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]).
"Closed-form solution?" The path count equals C(m+n-2, m-1). Mention it shows this is essentially Pascal's triangle and note potential overflow for large inputs (use BigInt or the rolling DP instead).
"What if the robot can also move left or up?"The DAG structure breaks — you'd need BFS/DFS or memoization on a graph (and cycles make it ill-defined). Clarify constraints before coding.

OPTIMAL 2D DP

uniquePaths.ts
function uniquePaths(m: number, n: number): number {
  // dp[i][j] = number of unique paths to reach row i, col j
  const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1));

  // Top row and left column are already seeded to 1 (fill(1) above).
  // Only one way to reach any edge cell: go straight.

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
}

// O(1)-space rolling optimisation: one row is enough.
function uniquePathsO1(m: number, n: number): number {
  let row = Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1]; // row[j] holds "from above"; row[j-1] just became "from left"
    }
  }
  return row[n - 1];
}

// Combinatorial closed form: C(m+n-2, m-1)
function uniquePathsMath(m: number, n: number): number {
  // Robot takes exactly (m-1) down-steps and (n-1) right-steps = m+n-2 total.
  // Choose which m-1 of them are down-steps.
  const total = m + n - 2;
  const choose = m - 1;
  let result = 1;
  for (let i = 0; i < choose; i++) {
    result = (result * (total - i)) / (i + 1);
  }
  return Math.round(result);
}

ALT 1 Brute force — recurse on every move

O(2^(m+n)) time · O(m+n) space

Walk the grid by raw recursion: from each cell branch into "go down" and "go right", count 1 whenever you land on the corner, and sum the branches — the definition of the problem with no table.

approach-2.ts
function uniquePaths(m: number, n: number): number {
  // paths(i, j) = number of ways to reach the bottom-right from cell (i, j).
  const paths = (i: number, j: number): number => {
    if (i === m - 1 && j === n - 1) return 1; // reached the corner: one way
    if (i >= m || j >= n) return 0;           // walked off the grid: dead end
    // Branch: step down, then step right, and total the routes.
    return paths(i + 1, j) + paths(i, j + 1);
  };

  return paths(0, 0);
}

Note → Each call spawns two more, so the recursion tree is exponential and recomputes the same (i, j)cells over and over. Memoizing those overlapping subproblems — or filling them bottom-up as a table — collapses it to the O(m·n) DP; the binomial formula does it in O(min(m,n)).

MNEMONIC The one-liner

"Every interior cell is the sum of the cell above it and the cell to its left — seed the edges to 1 and let it flow."

TRIGGERS When you see _ → reach for _

grid, can only move right/down	2D DP, dp[i][j] = dp[i-1][j] + dp[i][j-1]
count distinct paths on a grid	seed edges to 1, fill interior
"reduce space to O(n)"	rolling single row: row[j] += row[j-1]
closed-form / combinatorics	C(m+n-2, m-1) — choose down-steps

SKELETON The reusable shape

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

FLASHCARDS Tap to flip

What does dp[i][j] represent?

The number of unique paths from the top-left corner (0,0) to cell (i, j).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For m=3, n=3, what is the answer?

QUESTION 02

What is the recurrence relation for an interior cell?

QUESTION 03

What are the correct base-case values, and why?

QUESTION 04

The O(1)-space rolling-row update is:

QUESTION 05

What is the time complexity of the 2D DP solution?

QUESTION 06

The combinatorial closed form for m=4, n=4 is:

QUESTION 07

In Unique Paths II (with obstacles), what changes?

QUESTION 08

#62 · Unique PathsA robot on an m×n grid can only move right or down — count every distinct route to the bottom-right corner with dp[i][j] = dp[i-1][j] + dp[i][j-1], reducible to one rolling row or a single binomial coefficient.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Every cell is reachable from exactly two directions

RECURRENCE Build the DP table

COST Complexity & space reduction

Rolling row

Combinatorial closed form

RUN IT Fill the DP grid row by row

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL 2D DP

ALT 1 Brute force — recurse on every move

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _