62. Unique Paths

Unique Paths is the cleanest on-ramp to grid dynamic programming: the state is a cell, the recurrence is one addition, and once you see it every other “walk the grid” DP looks the same. It sits in the 2D dynamic programming pattern, so the table you build here is the shape you’ll reuse in a dozen harder problems.

The problem

A robot starts at the top-left corner of an m x n grid and wants to reach the bottom-right corner, moving only right or down at each step. Count how many distinct paths get it there. (Full statement on LeetCode.)

Take a 3 x 2 grid (3 rows, 2 columns). The robot can go down-down-right, down-right-down, or right-down-down — three paths, no more.

Intuition: every cell sums its two doors

There are only two ways to arrive at any cell: step down from the cell above it, or step right from the cell to its left. Those two arrivals never overlap, because the last move that landed you there was different. So the number of ways to reach cell (i, j) is just the ways to reach the cell above plus the ways to reach the cell on the left:

$\text{paths}(i, j) = \text{paths}(i-1, j) + \text{paths}(i, j-1)$

The edges anchor the recurrence. The entire top row and entire left column have exactly one way in — you can only stream straight along them without ever turning — so they’re all 1. Every interior cell then falls out of the addition.

If you like closed forms, the answer is also the binomial coefficient $\binom{m+n-2}{m-1}$: any path is a fixed sequence of $m-1$ downs and $n-1$ rights, and you’re just choosing which positions are the downs. Worth naming in an interview, but the DP table is what generalizes when obstacles or weights show up.

Solution

The natural version fills a full 2D table, cell by cell:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // Top row and left column: exactly one straight-line path each.
        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];   // from above + from the left
            }
        }
        return dp[m - 1][n - 1];
    }
}

Notice each row only ever reads the row directly above it and the value just written to its left. That means you don’t need the whole grid — a single row, updated in place, carries everything. When you compute dp[j], the slot still holds the old value (the cell above), and dp[j - 1] already holds the freshly updated cell to the left:

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);            // first row: all ones

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];    // (above, still in dp[j]) + (left, updated)
            }
        }
        return dp[n - 1];
    }
}

Complexity

Approach	Time	Space
Full 2D table	$O(mn)$	$O(mn)$
Rolling 1D row	$O(mn)$	$O(n)$

Both visit every cell once, so time is $O(mn)$ either way. The rolling version keeps only one row, dropping space to $O(n)$ — and you can shrink it further by iterating over the smaller dimension.

In an interview

Say the recurrence in one breath before writing anything: “you reach a cell only from above or from the left, so it’s the sum of those two, and the top edge and left edge are all ones.” That single sentence proves you found the subproblem, which is the part being graded. The trap is the base case — forget to seed the first row and column to 1 and every path collapses to zero. If the interviewer nudges you on space, reach for the rolling row and explain why reading dp[j] before you overwrite it is the cell above.

The same fill-the-grid table drives Longest Common Subsequence, where each cell instead compares two characters and reaches back diagonally; the 2D DP hub walks through where this shape keeps showing up.

References

• LeetCode 62 — Unique Paths