Unique Paths (LC 62)

Pattern: Dynamic Programming - Grid Path
Difficulty: Medium
Key Concept: dp[i][j] = dp[i-1][j] + dp[i][j-1] — paths from above + paths from left

1. Problem Statement

There is a robot on an m x n grid. The robot starts at the top-left corner (0, 0) and tries to move to the bottom-right corner (m - 1, n - 1).

The robot can only move down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths to the bottom-right corner.

Constraints (typical):

• 1 <= m, n <= 100

---

2. Algorithm (2D DP)

Idea: To reach cell (i, j), the robot must have come from (i-1, j) or (i, j-1). So the number of paths to (i, j) is the sum of paths to those two neighbors.

Pseudocode:

dp = m x n grid of zeros
for i in 0..m-1:
    for j in 0..n-1:
        if i == 0 OR j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]

Boundary: first row and first column each have exactly one path (only rights or only downs).

---

3. Beginner Analysis — Why dp[i][j] = dp[i-1][j] + dp[i][j-1]

• Every path to (i, j) ends with either a down step from (i-1, j) or a right step from (i, j-1).
• Those two sets of paths are disjoint (last move differs), and every path to (i, j) ends one of those two ways.
• So: total paths = paths to cell above + paths to cell left.
• Base case: along the top row or left column there is no choice — only one route along the edge — hence 1 for those cells.

---

4. Dry Run — m = 3, n = 3

DP table (dp[i][j] = paths to (i,j)):

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

• (1,1) = (0,1)+(1,0) = 1+1 = 2
• (1,2) = (0,2)+(1,1) = 1+2 = 3
• (2,2) = (1,2)+(2,1) = 3+3 = **6**

Answer: 6 unique paths.

---

5. Brute Force Java — Recursion O(2^(m+n))

class SolutionBrute {
    public int uniquePaths(int m, int n) {
        return dfs(0, 0, m, n);
    }

    private int dfs(int i, int j, int m, int n) {
        if (i == m - 1 && j == n - 1) {
            return 1;
        }
        if (i >= m || j >= n) {
            return 0;
        }
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
}

---

6. Optimal Java — 2D DP, 1D DP, and Math (nCr)

2D DP — O(m·n) time, O(m·n) space (interview-safe):

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

1D DP — O(m·n) time, O(n) space:

class Solution1D {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

Math: Total moves = (m-1) + (n-1); choose which (m-1) are down (or (n-1) are right): C(m+n-2, m-1).

class SolutionMath {
    public int uniquePaths(int m, int n) {
        return nCr(m + n - 2, m - 1);
    }

    private int nCr(int n, int k) {
        if (k > n - k) {
            k = n - k;
        }
        long res = 1;
        for (int i = 0; i < k; i++) {
            res = res * (n - i) / (i + 1);
        }
        return (int) res;
    }
}

---

7. Java & Language Tricks

Topic	Note
No built-in nCr	Implement multiplicative formula with long intermediates to reduce overflow risk.
long for factorial-style products	int overflows quickly for larger m,n in combinatorial formulas.
2D DP	Clearest for interviews; easy to explain and extend.
1D row rolling	Same recurrence, overwrites row left-to-right.

---

8. Complexity

Approach	Time	Space
Brute DFS (no memo)	O(2^(m+n))	O(m+n) stack
2D DP	O(m·n)	O(m·n)
1D DP	O(m·n)	O(n)
Math C(m+n-2, m-1)	O(min(m,n)) with multiplicative nCr	O(1)