4.24.1 — Unique Paths

LeetCode 62 · Medium · ★ Blind 75

The problem

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

m = 3, n = 7   →  28
m = 3, n = 2   →  3

The pattern

Same question as every DP: how did I get here?

You can only arrive at a cell from the left or from above. Those two routes are disjoint and cover everything, so:

dp[r][c] = dp[r-1][c] + dp[r][c-1]

Counting, so the operator is + — this is 4.23.1 Climbing Stairs in two dimensions.

The base cases are the first row and the first column, which all hold 1: there is exactly one way to reach any cell in the top row (keep going right) and any cell in the left column (keep going down).

The fill order

This is what 2-D DP is really about, so it is worth stating explicitly even on an easy problem.

dp[r][c] reads dp[r-1][c] and dp[r][c-1] — both a smaller row or a smaller column. So filling top to bottom, left to right guarantees every cell it needs is already there.

Always check this before writing the loops. List what the recurrence reads, and choose an order where those cells come first. Half of all 2-D DP bugs are reading a cell that has not been filled.

The solution

Python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n                        # the top row: one way to each cell

        for _ in range(1, m):
            for c in range(1, n):
                row[c] += row[c - 1]         # from above (old) + from the left (new)

        return row[-1]

TypeScript

function uniquePaths(m: number, n: number): number {
  const row = new Array(n).fill(1);

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      row[c] += row[c - 1];
    }
  }

  return row[n - 1];
}

row[c] += row[c - 1] is the rolled-array version, and it is worth unpacking because the same line appears throughout this chapter.

At the moment the line runs:

• row[c] still holds the value from the previous row — that is the "from above" term.
• row[c - 1] has already been updated in this row — that is the "from the left" term.

So one array does the job of two, and the update reads exactly the two cells the recurrence needs. This only works because the loop goes left to right; reversing it would read the wrong row[c-1].

The full-table version is easier to see first:

dp = [[1] * n for _ in range(m)]
for r in range(1, m):
    for c in range(1, n):
        dp[r][c] = dp[r-1][c] + dp[r][c-1]
return dp[m-1][n-1]

O(mn) time, O(mn) space. Write this, then collapse to the single row and say why the collapse is legal.

The maths answer

You need exactly m − 1 downs and n − 1 rights, in some order, for a total of m + n − 2 moves. Choosing which of them are downs determines the path entirely:

\binom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!\,(n-1)!}

O(\min(m,n)) time and O(1) space, computing the binomial coefficient iteratively to avoid huge factorials.

Mention it — it is the fastest answer and shows you looked at the structure rather than reaching for a table. Then note the catch: it only works because the grid is empty. Add a single obstacle and the combinatorics collapses while the DP needs one extra line.

Where this goes next

• Unique Paths II — some cells are blocked. Set dp[r][c] = 0 for an obstacle, since no path can pass through it. One line, and the maths solution is gone.
• Minimum Path Sum — the cheapest route rather than the count. + becomes min, and you add the cell's own cost.
• Unique Paths III — visit every empty cell exactly once. That is Hamiltonian, so it is backtracking, not DP. A good reminder that a similar-sounding problem can be in a completely different complexity class.
• Dungeon Game — the same grid filled backwards from the destination, because the constraint is about surviving the rest of the journey rather than what happened so far.

What the interviewer will push on

"Derive the recurrence." Arrive from the left or from above; disjoint and complete.

"What are the base cases?" The first row and first column, all 1.

"Why does the loop go in that order?" Every cell reads a smaller row and a smaller column.

"Can you use O(n) space?" One row, and explain what row[c] and row[c-1] hold at the moment of the update.

"Is there a closed form?" The binomial coefficient — and it stops working the moment obstacles appear.

One thing to volunteer: state the fill order and why before writing the loops. On this problem it is easy; on 4.24.10 Burst Balloons it is the entire difficulty, and building the habit here is what makes that one manageable.

Next: 4.24.2 Longest Common Subsequence — the grid that compares two strings, and the template for six more problems.