Unique Paths

1. Problem & Core Objective

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

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

Constraints: 1 <= m, n <= 100 · the answer is guaranteed to fit in a 32-bit integer

What's actually being tested: the 2-D analogue of Climbing Stairs — dp[i][j] = dp[i−1][j] + dp[i][j−1]. It establishes the grid DP shape, the row-rolling optimisation, and the fact that this particular problem has a closed-form answer, which most don't.

2. First-Principles Thought Process

Reason from the last move, again

To stand on cell (i, j), the robot's final move came from above (i−1, j) or from the left (i, j−1). Those are the only options and they're mutually exclusive.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Counting, so the combiner is +.

The base cases are the edges

The top row and left column each have exactly one path — straight along the edge, since you can't move up or left.

for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 0; i < m; i++) dp[i][0] = 1;

Equivalently, seed dp[0][0] = 1 and let the recurrence handle the rest by treating out-of-range as 0.

The dependencies decide everything

dp[i][j] reads only the cell above and the cell left. So filling row by row, left to right, always has both ready.

And since only row i−1 is read, a single row suffices — with j ascending, dp[j] still holds the previous row's value when read, and dp[j-1] already holds the current row's.

dp[j] += dp[j - 1];        // dp[j] is "above", dp[j-1] is "left"

That one line is the entire rolled recurrence, and it's worth unpacking rather than memorising.

The closed form

Every path makes exactly m − 1 downs and n − 1 rights, in some order. So the count is the number of ways to arrange them:

C(m + n − 2, m − 1)

For m = 3, n = 7: C(8, 2) = 28 ✓

That's O(min(m,n)) with no DP at all — but it needs care with overflow, which is the catch.

3. Solution Paths

Approach 1 — Recursion

public int uniquePaths(int m, int n) {
    return paths(m - 1, n - 1);
}

private int paths(int i, int j) {
    if (i == 0 || j == 0) return 1;                 // along an edge: one path
    return paths(i - 1, j) + paths(i, j - 1);
}

• Time O(2^(m+n)) · Space O(m + n) stack

Counter-questions on this approach

⭐ "Why exponential?"

Two branches per cell and heavy overlap — paths(i-1, j-1) is reached from both paths(i-1, j) and paths(i, j-1), and recomputed each time.

There are only m × n = 10,000 distinct cells, so memoising collapses it immediately. At m = n = 100 the naive version is 2^200.

⭐ "Why does an edge cell return 1?"

On the top row you can only move right, so there's exactly one path. Same on the left column.

It's the 2-D analogue of dp[0] = 1 in the 1-D problems: the degenerate case has exactly one way, not zero.

Approach 2 — 2-D tabulation

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    for (int j = 0; j < n; j++) dp[0][j] = 1;       // top row
    for (int i = 0; i < m; i++) dp[i][0] = 1;       // left column

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

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

Trace — m = 3, n = 3:

dp[1][1] = 1 + 1 = 2, dp[2][2] = 3 + 3 = 6 ✓

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why is filling row by row, left to right, the correct order?"

Because dp[i][j] reads dp[i-1][j] — the row above, already complete — and dp[i][j-1] — the cell to the left in the current row, already computed.

Any order satisfying those two dependencies works; row-major is the natural one. Column-major would work equally well by symmetry.

"Could the count overflow?"

C(198, 99) is astronomically large, so in general yes — but the problem guarantees the answer fits in a 32-bit integer, which bounds the usable inputs.

At m = n = 100 the true count is about 2.3 × 10^58, so that guarantee means the test data never reaches the stated constraint corners. Worth noticing: the constraints and the guarantee together are narrower than the constraints alone suggest.

Approach 3 — Single-row rolling (optimal DP)

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);                             // the top row

    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[j] += dp[j - 1];                     // above + left

    return dp[n - 1];
}

• Time O(m · n) · Space O(n)

Counter-questions on this approach

⭐ "Unpack dp[j] += dp[j - 1]. Which values are those?"

At the moment of the read, dp[j] still holds the previous row's value at column j — that's dp[i-1][j], the cell above. And dp[j-1] was already overwritten during this row, so it holds dp[i][j-1], the cell to the left.

So the line is exactly dp[i][j] = dp[i-1][j] + dp[i][j-1], with the array doing double duty.

This is the kind of line worth deriving rather than copying, because it's opaque otherwise.

⭐ "Why must j ascend here?"

Because the current row's dp[j-1] must already be updated — that's the "left" term. Descending would read the previous row's value there, computing something else entirely.

Contrast with 0/1 knapsack, where descending is required precisely to avoid reading the current row. The direction is dictated by which neighbours the recurrence needs, not by convention.

"Why Arrays.fill(dp, 1) rather than just dp[0] = 1?"

Because the initial array represents the top row, where every cell has exactly one path. Filling with 1s seeds it correctly.

And dp[0] stays 1 throughout, which is right — the left column always has one path, and the inner loop starts at j = 1 so it's never overwritten.

"Could you roll to O(min(m,n))?"

Yes — swap so the shorter dimension is the row length. if (m < n) return uniquePaths(n, m); at the top. The grid is symmetric under transposition, so the answer is unchanged.

Approach 4 — Closed-form combinatorics

public int uniquePaths(int m, int n) {
    long result = 1;
    // C(m+n-2, m-1), computed to avoid overflow
    for (int i = 1; i <= m - 1; i++)
        result = result * (n - 1 + i) / i;
    return (int) result;
}

• Time O(min(m, n)) · Space O(1)

Counter-questions on this approach

⭐ "Why is the answer a binomial coefficient?"

Every path makes exactly m − 1 down-moves and n − 1 right-moves, in some order. A path is an arrangement of those moves, so the count is the number of ways to choose which m − 1 of the m + n − 2 steps are downs — C(m+n−2, m−1).

For m = 3, n = 7: C(8, 2) = 28 ✓

⭐ "Why compute it incrementally rather than as factorial(a) / (factorial(b) * factorial(c))?"

Because factorial(198) overflows anything short of BigInteger long before the division would bring it back down.

The incremental form multiplies and divides alternately, keeping the running value near the final answer. And each intermediate result * (n-1+i) is exactly divisible by i — a property of binomial coefficients — so the integer division is exact at every step, not just at the end.

That exactness is worth stating: it's why integer arithmetic is safe here rather than needing rationals.

"Is long enough?"

For answers that fit in int, yes — the intermediate result * (n-1+i) is at most about 200 × the final answer, so with the answer under 2^31 the product stays under 2^39. Comfortably inside long.

If the answer could be large, this breaks too and you'd need BigInteger.

"Would you submit this?"

I'd mention it and submit the DP. The closed form is faster and uses no memory, but it's specific to this grid — the moment obstacles appear (LeetCode 63), the combinatorics collapses and the DP survives unchanged with one extra line.

That generality is worth more than the constant factor here.

Comparison

4. Why the Optimal Wins

The recursion recomputes the same m × n cells exponentially often. The table fixes that; rolling removes a dimension because only the previous row is read.

The closed form is asymptotically best and I'd mention it — but the DP is the answer worth writing, because it survives the obvious follow-up (obstacles) that destroys the combinatorial argument.

The framing worth keeping:

dp[i][j] = dp[i−1][j] + dp[i][j−1] — above plus left. Only the previous row is read, so one array suffices with j ascending, where dp[j] is still "above" and dp[j−1] is already "left".

5. Java Prerequisites

The rolled grid recurrence

int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
    for (int j = 1; j < n; j++)
        dp[j] += dp[j - 1];        // dp[j] = above (stale), dp[j-1] = left (fresh)

j ascending because the "left" term must be the current row. Descending would read the previous row there.

Incremental binomial — multiply then divide, keeping the running value small:

result = result * (n - 1 + i) / i;     // exact at every step

factorial first would overflow.

6. Interview Communication Guide

Clarifying questions: Only down and right (yes)? Any obstacles (no — LC 63 is that variant)? Does the answer fit in int (guaranteed)? Can m or n be 1 (yes — one path)?

The pitch

"Reasoning from the last move: to be on cell (i,j), the robot came from above or from the left. Those are the only options and they're disjoint, so dp[i][j] = dp[i-1][j] + dp[i][j-1] — counting, so the combiner is addition.

The base cases are the top row and left column, each with exactly one path, since along an edge there's no choice.

Filling row by row, left to right, satisfies both dependencies — the row above is complete and the cell to the left was just computed.

And since only the previous row is read, one array suffices. The rolled line is dp[j] += dp[j-1], which is worth unpacking: at that moment dp[j] still holds the previous row's value — the cell above — while dp[j-1] was already overwritten this row, so it's the cell to the left.

j must ascend for that to work. Contrast with 0/1 knapsack, where descending is required precisely to avoid reading the current row — the direction is dictated by which neighbours you need.

O(m·n) time, O(n) space, and I'd swap so the shorter dimension is the row length.

There's also a closed form: every path is m−1 downs and n−1 rights in some order, so the answer is C(m+n−2, m−1) — O(min(m,n)) with no memory. I'd compute it incrementally, multiplying and dividing alternately, because the factorials overflow otherwise, and each step's division is exactly divisible, which is a property of binomial coefficients.

I'd still submit the DP though. The combinatorics is specific to an unobstructed grid — add a single obstacle and it collapses, while the DP needs one extra line."

Edge cases to volunteer:

Name m = n = 1. The answer is 1, not 0 — you're already there, and the empty path counts. It's the 2-D version of dp[0] = 1.

7. Follow-Up Questions — Modified Constraints

⭐ "Add obstacles to the grid."

LeetCode 63. dp[i][j] = 0 for an obstacle, and the recurrence is otherwise unchanged. One extra line.

The closed form dies completely — there's no combinatorial expression for paths around arbitrary obstacles. That's the argument for writing the DP.

⭐ "Allow diagonal moves as well."

dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1] — Delannoy numbers. The rolled version needs the diagonal too, which means saving dp[j-1] before it's overwritten. Still O(n) space with one extra variable.

"Find the minimum-cost path rather than counting paths."

Change + to min and add the cell's cost — Minimum Path Sum (LC 64). Same structure, optimisation combiner, exactly the substitution from Min Cost Climbing Stairs.

"What if m and n were 10^5?"

O(m·n) = 10^10 is infeasible, and the answer would need BigInteger. The closed form is O(min(m,n)) and works — but only because there are no obstacles. That's the case where the combinatorics is the only option.

"Return one actual path."

Trivial — any interleaving works, so emit m−1 downs and n−1 rights in any order. Worth noticing that finding a path is far easier than counting them.

"Count paths that avoid the main diagonal."

Catalan numbers, C(2k, k)/(k+1) for a square grid. A classic result, and it shows the combinatorial route extends to some constraints — just not arbitrary ones.