Unique Paths LeetCode 62 Deep Dive

LeetCode 62 Unique Paths presents a classic combinatorics and dynamic programming challenge. A robot is placed at the top-left corner of an m x n grid and must reach the bottom-right corner. The robot can only move in two directions at any step: right or down. Your task is to count the total number of unique paths from the start to the destination.

The constraint that the robot can only move right or down is what makes this problem tractable. It eliminates the possibility of cycles and guarantees that every path has exactly (m-1) down moves and (n-1) right moves — a total of m+n-2 moves. This observation is the bridge between the DP and the combinatorics approach.

LeetCode 62 is the foundational grid DP problem and appears in virtually every dynamic programming curriculum. Understanding its three solution approaches — 2D DP, 1D space-optimized DP, and the math formula — builds the intuition needed for minimum path sum, unique paths II with obstacles, and other grid traversal problems.

The 2D dynamic programming approach defines dp[i][j] as the number of unique paths to reach cell (i, j) from (0, 0). Since the robot can only move right or down, it can arrive at (i, j) from either (i-1, j) directly above or (i, j-1) directly to the left. The recurrence is therefore dp[i][j] = dp[i-1][j] + dp[i][j-1].

Base cases are straightforward: every cell in the first row has exactly one path to it (move right repeatedly from the start), so dp[0][j] = 1 for all j. Similarly, every cell in the first column has exactly one path (move down repeatedly), so dp[i][0] = 1 for all i. After initializing the borders, fill the grid row by row from top-left to bottom-right, and the answer is dp[m-1][n-1].

This approach has O(m*n) time complexity — every cell is computed exactly once in constant time — and O(m*n) space complexity for the grid. For m, n up to 100 this is a 10,000-element array, completely practical. The 2D table also makes it easy to trace through and verify your answer by inspecting intermediate values.

The 2D DP solution uses O(m*n) space, but notice that when computing row i, you only ever look at row i-1. The rest of the grid is never referenced again. This observation enables a space optimization: instead of maintaining the full m x n table, maintain a single 1D array dp of length n representing the current row being computed.

Initialize dp = [1, 1, ..., 1] (all ones, representing the first row). For each subsequent row, iterate left to right and update dp[j] += dp[j-1]. Before this update, dp[j] holds the value from the previous row (the cell above), and dp[j-1] holds the already-updated value of the current row to the left. After the update, dp[j] = dp[j] (old, from row above) + dp[j-1] (current row, left neighbor) — exactly the 2D recurrence.

The result after processing all m rows is dp[n-1], which equals the bottom-right value. Time complexity remains O(m*n), but space complexity drops to O(n). If n > m, you can swap the roles of m and n to use O(min(m,n)) space — always iterate over the longer dimension and keep the shorter one in the array.

Every path from (0,0) to (m-1, n-1) requires exactly (m-1) down moves and (n-1) right moves, for a total of (m-1)+(n-1) = m+n-2 moves. The number of unique paths equals the number of ways to choose which m-1 of those m+n-2 moves are "down" (the rest are automatically "right"). This is the combination C(m+n-2, m-1).

For example, with m=3 and n=7: total moves = 2+6 = 8, choose 2 to be down. C(8, 2) = 8!/(2! * 6!) = (8*7)/(2*1) = 28. No grid, no iteration over cells — just one formula evaluation. The time complexity is O(min(m,n)) for the iterative computation of the binomial coefficient, and space complexity is O(1).

Computing the combination efficiently requires care to avoid integer overflow and large intermediate values. The iterative approach multiplies and divides alternately: for C(n, k) with k = min(k, n-k), compute the product of (n-i)/(i+1) for i from 0 to k-1, performing integer division at each step. In Python, arbitrary-precision integers and math.comb make this trivial; in Java, you must be deliberate about the computation order.

With m=3 rows and n=7 columns, the math solution gives C(m+n-2, m-1) = C(8, 2) = 28. This is the answer in a single formula evaluation. To verify using the 2D DP grid: initialize the first row and first column all to 1. Then fill in the remaining cells using dp[i][j] = dp[i-1][j] + dp[i][j-1].

Row 0 (base): [1, 1, 1, 1, 1, 1, 1]. Row 1: start with dp[1][0]=1, then dp[1][1]=1+1=2, dp[1][2]=2+1=3, dp[1][3]=3+1=4, dp[1][4]=4+1=5, dp[1][5]=5+1=6, dp[1][6]=6+1=7. Row 2: start with dp[2][0]=1, then dp[2][1]=1+2=3, dp[2][2]=3+3=6, dp[2][3]=6+4=10, dp[2][4]=10+5=15, dp[2][5]=15+6=21, dp[2][6]=21+7=28.

The bottom-right value dp[2][6] = 28, matching C(8,2) exactly. The 1D approach would track dp = [1,1,1,1,1,1,1] then update to [1,2,3,4,5,6,7] for row 1, then to [1,3,6,10,15,21,28] for row 2, with the final answer dp[6] = 28. All three approaches converge on the same result.

Python 2D DP: initialize dp = [[1]*n for _ in range(m)], then for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1]; return dp[m-1][n-1]. Python 1D DP: dp = [1]*n, then for _ in range(m-1): for j in range(1, n): dp[j] += dp[j-1]; return dp[n-1]. Python math: import math; return math.comb(m+n-2, m-1) — the entire solution in one line using Python 3.8+ built-in.

Java 2D DP: int[][] dp = new int[m][n]; fill first row and column with 1; nested loops for the remaining cells. Java 1D DP: int[] dp = new int[n]; Arrays.fill(dp, 1); outer loop m-1 times, inner loop j from 1 to n-1 with dp[j] += dp[j-1]; return dp[n-1]. Java math: use long arithmetic, iterate k from 0 to min(m,n)-2, multiplying and dividing to compute C(m+n-2, min(m-1,n-1)).

All three Python versions are concise; the math version is a one-liner. Java requires more care, especially for the math version — computing C(n,k) iteratively as a running product, using long to prevent overflow, and choosing k = min(m-1, n-1) to minimize the number of multiplications. For the given constraints (m,n <= 100), even int arithmetic is safe, but using long is a good defensive habit.

LeetCode 64 Minimum Path Sum is the closest relative: same grid, same right-or-down movement, but instead of counting paths you minimize the sum of values along the path. The recurrence becomes dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), and the 1D space optimization applies identically. Unique Paths is the building block — if you understand it, minimum path sum follows immediately.

LeetCode 63 Unique Paths II adds obstacles: certain cells are blocked and no path can pass through them. The recurrence is the same, but dp[i][j] = 0 whenever grid[i][j] == 1 (obstacle), and boundary initialization must also check for obstacles. LeetCode 931 Minimum Falling Path Sum extends the pattern to a square grid where you can move to any of three cells below (down-left, down, down-right).

The grid DP family includes triangle path (LeetCode 120, minimize path from top to bottom of a triangle), cherry pickup (LeetCode 741, two-pass grid DP), and dungeons game (LeetCode 174, reverse DP from bottom-right). All share the same core idea: define a DP state per cell, express it in terms of a small set of neighbors, and fill systematically. Unique Paths is the cleanest entry point into this family.