Unique Paths (LC 62)

Pattern: 2-D Grid DP Difficulty: Medium Key Concept: dp[i][j] = ways to reach cell (i, j) = dp[i-1][j] + dp[i][j-1]. Robot only moves right or down.

Problem Statement

A robot starts at the top-left corner of an m × n grid. It can only move right or down. Return the number of distinct paths to the bottom-right corner.

Example

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

---

1. Algorithm & Pseudocode

2-D DP

dp[i][j] = ways to reach cell (i, j)

dp[0][*] = 1   (only one way along the top row: keep going right)
dp[*][0] = 1   (only one way along the left col: keep going down)
dp[i][j] = dp[i-1][j] + dp[i][j-1]

answer = dp[m-1][n-1]

Space-optimized 1-D DP

Only the previous row is needed. Roll prev[n] and curr[n] (or update in place: dp[j] += dp[j-1]).

Math — Combinatorics

The robot makes (m-1) + (n-1) total moves, of which (m-1) are “down” — so the answer is C(m+n-2, m-1).

---

2. Step-by-Step Analysis

Why the recurrence works To stand on cell (i, j), the robot’s previous cell was either directly above (i-1, j) or directly to the left (i, j-1). These two sets of paths are disjoint, so add their counts.

Why row 0 and col 0 are all 1s Only one path: keep going straight.

Why the 1-D rolling trick works When computing dp[i][j]:

• Before update, dp[j] still holds dp[i-1][j] (the row above).
• dp[j-1] was just updated to dp[i][j-1] (this row, left neighbor).
• So dp[j] = dp[j] + dp[j-1] matches the 2-D recurrence.

ASCII Trace for m=3, n=3

2-D DP:
1  1  1
1  2  3
1  3  6   ← answer

---

3. The Dry Run

m = 3, n = 3

i\j	0	1	2
0	1	1	1
1	1	2	3
2	1	3	6

dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6.

---

4. Java Solution

2-D DP

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        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];
    }
}

Optimal — 1-D DP

class Solution {
    public int uniquePaths(int m, int n) {
        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];
            }
        }
        return dp[n - 1];
    }
}

Time: (O(m \cdot n)) Space: (O(n))

Combinatorics

class Solution {
    public int uniquePaths(int m, int n) {
        long result = 1;
        for (int i = 1; i < m; i++) {
            result = result * (n - 1 + i) / i;   // multiply first to avoid integer truncation
        }
        return (int) result;
    }
}

Time: (O(\min(m, n))) Space: (O(1))

---

5. The “Java vs. Others” Edge

• Use long in the combinatorics version to avoid overflow during the running product.
• Arrays.fill(dp, 1) initializes the whole 1-D DP row in one call.
• For the obstacle follow-up (LC 63), set dp[j] = 0 whenever an obstacle is at (i, j).

---

6. Complexity Summary

Approach	Time	Space	Notes
2-D DP	O(m × n)	O(m × n)	Straightforward
1-D Rolling DP	O(m × n)	O(n)	Cleanest practical solution
Combinatorics	O(min m,n)	O(1)	Fastest if math allowed