LeetCode Unique Paths: Grid DP and Math

LeetCode 62 — Unique Paths — is the friendliest grid DP problem and one of the few interview questions with a clean closed-form answer. The DP is a one-paragraph derivation; the math is a one-line answer. Knowing both signals breadth, but only one of them is the right thing to write down first.

The Problem

A robot sits in the top-left cell of an m x n grid. It can move only right or down. Return the number of distinct paths from the top-left cell to the bottom-right cell.

Brute Force

Recurse. Let f(r, c) be the number of paths from (r, c) to (m - 1, n - 1). Base case: at the goal, return 1. Recurrence: f(r, c) = f(r + 1, c) + f(r, c + 1), taking out-of-bounds as 0.

def uniquePaths(m, n):
    def f(r, c):
        if r == m - 1 and c == n - 1:
            return 1
        total = 0
        if r + 1 < m:
            total += f(r + 1, c)
        if c + 1 < n:
            total += f(r, c + 1)
        return total
    return f(0, 0)

Without memoization this blows up — it is essentially counting paths by re-walking them.

Optimal Solution

Tabulate. Let dp[r][c] be the number of paths from (0, 0) to (r, c). Initialize dp[0][c] = 1 for all c (a single path going right) and dp[r][0] = 1 for all r (a single path going down). For interior cells, dp[r][c] = dp[r - 1][c] + dp[r][c - 1].

def uniquePaths(m, n):
    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]

Space drops to O(n) with a single row that you overwrite in place:

def uniquePaths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[n - 1]

The closed form: every path takes m + n - 2 steps, of which m - 1 are downward. The number of such paths is the binomial coefficient C(m + n - 2, m - 1).

from math import comb

def uniquePaths(m, n):
    return comb(m + n - 2, m - 1)

Walk Through an Example

For a 3 x 7 grid:

The DP fills row by row:

1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28

Answer: 28. The closed form agrees: C(8, 2) = 28.

The 1D rolling version computes the third row directly by repeatedly adding the running prefix sum to each cell — same numbers, half the memory.

Edge Cases

• A 1 x n or m x 1 grid — only one path. The base-row initialization handles this. The closed form gives C(n - 1, 0) = 1.
• m = n = 1 — the robot is already at the goal. Answer is 1.
• Very large grids — the DP uses big arrays; the closed form is a single integer computation. Python handles big ints natively. In C++ you would need a careful multiplicative loop to avoid overflow.

Complexity Analysis

The 2D DP is O(m * n) time and O(m * n) space. The 1D rolling version is O(m * n) time and O(n) space. The closed form is O(min(m, n)) time using a multiplicative binomial — or even O(1) if you accept Python’s arbitrary precision arithmetic as a single step.

The brute force without memoization is exponential because it counts paths by enumerating them. For more on why DP collapses exponential recursion into polynomial work, see DP: Introduction.

How to Explain It in an Interview

Open with the recurrence in plain English: “Every cell other than the start can be reached from above or from the left, so its path count is the sum of those two.” Write the 2D DP. Volunteer the rolling optimization without being asked — it costs one line of code and demonstrates space awareness.

Only then mention the closed form: “We are choosing which m - 1 of m + n - 2 steps go down, so the answer is C(m + n - 2, m - 1).” Calling this out establishes that you know the math but did not skip past the DP that the interviewer wanted to see. Avoid the temptation to write only the closed form; many interviewers will count that as ducking the question.

Related Problems

• LeetCode 63 — Unique Paths II (obstacles; closed form no longer applies)
• LeetCode 64 — Minimum Path Sum
• LeetCode 980 — Unique Paths III (backtracking, every cell must be visited)
• LeetCode 174 — Dungeon Game

Notice how adding even one obstacle removes the closed form — that is a useful reminder that combinatorial shortcuts are fragile.

Wrap up

Unique Paths is the grid-DP starter pack. Lock in three artifacts: the 2D table, the 1D rolling row, and the binomial formula. Pair this problem with Classic DP Problems and you will be fluent in the prefix-sum-on-a-grid style that powers half of dynamic programming interviews. Then, when the variant with obstacles shows up, you already know exactly which line in the recurrence to guard.