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

Constraints:

• 1 <= m, n <= 100
• The answer will be less than or equal to 2 * 10^9 (fits in a standard 32-bit integer).

Plain-English Restatement: Imagine you are playing a board game on a grid where you can only move your piece rightwards or downwards. You start at the top-left corner and want to find every possible unique sequence of moves that lands you at the bottom-right corner. Two paths are considered distinct if they differ by even a single move (e.g., going Right-Down is different from going Down-Right).

Brute Force Approach: The naive way to solve this is to simulate the robot's movement using Recursion (or Depth-First Search). From any cell (r, c), you would recursively call your function to go right (r, c+1) and down (r+1, c).

• Time Complexity: O(2^{m+n}). At almost every step, you branch into 2 possibilities. A path takes exactly (m-1) + (n-1) steps, so the recursion tree grows exponentially. For a 100x100 grid, 2^{200} is astronomically large and will instantly Time Out.
• Why it's wasteful: The recursion evaluates the exact same cells multiple times. If you go Right then Down, you end up at (1,1). If you go Down then Right, you also end up at (1,1). The brute force tree computes the paths from (1,1) to the end twice. DP solves this by saving the work.

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).

ELI5 Analogy: Imagine you're collecting water in a grid of buckets. Water can only flow into a bucket from the one directly above it, or the one directly to its left. If you want to know how much water ends up in a specific bucket, you just add together the water spilling in from the top bucket and the water spilling in from the left bucket. The "aha moment" is realizing you don't need to trace every drop from the source; you only care about your immediate neighbors.

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.

Code Walkthrough

1. Initialize the array: row = [1] * n creates our 1D DP table. Since we only ever need the "current" row and the "previous" row, we start by pretending this is row 0 (the top edge), where every cell has exactly 1 path to it.
2. Iterate through rows: for _ in range(1, m): starts at row 1 and goes down to the bottom.
3. Iterate through columns: for c in range(1, n): starts at column 1 (since column 0 is always 1 path straight down).
4. The Transition: row[c] += row[c - 1]. On the right side of the +=, row[c] is the value from the row above (because we haven't overwritten it yet), and row[c-1] is the value from the left (because we just updated it in the previous iteration of the loop).
5. Return result: row[-1] gives us the last element of the row, which corresponds to the bottom-right corner.

Hand Trace

Let's trace m = 3, n = 3.

1. Start: row = [1, 1, 1] (Represents Row 0).
2. Row 1:
   • c = 1: row[1] += row[0] → 1 + 1 = 2. row becomes [1, 2, 1].
   • c = 2: row[2] += row[1] → 1 + 2 = 3. row becomes [1, 2, 3].
3. Row 2:
   • c = 1: row[1] += row[0] → 2 + 1 = 3. row becomes [1, 3, 3].
   • c = 2: row[2] += row[1] → 3 + 3 = 6. row becomes [1, 3, 6].

Final array is [1, 3, 6]. The answer is row[-1] = 6.

Complexity Derivation

• Time Complexity: O(m \times n). We have two nested loops. The outer loop runs m-1 times, and the inner loop runs n-1 times. Inside the inner loop, we do a single O(1) addition. Therefore, we do a constant amount of work for each of the m \times n cells in the grid.
• Space Complexity: O(n). We only allocate a single 1D array of size n to store the previous row's results. (If we used the 2D matrix approach, space would be O(m \times n)).

Edge Cases

• 1D Grid (m = 1 or n = 1): The robot can only move in a straight line. The nested loops won't even execute, and it will just return the initialized 1. This correctly matches reality.

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.

"How would you handle a grid so large that the number of paths exceeds a 64-bit integer?" You would need to use a BigInt library (or Python's built-in arbitrary-precision integers). Alternatively, if they just want the answer modulo 10^9 + 7 (a common competitive programming constraint), you would simply apply % (10**9 + 7) at every addition step: row[c] = (row[c] + row[c-1]) % MOD.

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.