LeetCode 62 – Unique Paths | Love Me Some Coding

Unique Paths is the cleanest introduction to grid dynamic programming there is. No obstacles, no weights, no tie-breaking — just a robot, a rectangle, and a recurrence you can derive in one sentence. It is worth doing carefully, because the next two problems are this one with a single detail changed each time.

The problem

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

m = 3, n = 7  -> 28
m = 3, n = 2  -> 3      down-down-right, down-right-down, right-down-down
m = 1, n = 1  -> 1      already there; the empty path counts
m = 1, n = 10 -> 1      only one way to walk a corridor

The recurrence

Ask what the last move was. To stand on cell (r, c) the robot must have arrived either from the cell above or the cell to the left — there is no third way in, because those are the only two moves. So the paths to (r, c) are exactly the paths to (r-1, c) plus the paths to (r, c-1), and those two sets cannot overlap because they end with different moves.

paths[r][c] = paths[r-1][c] + paths[r][c-1]
paths[0][c] = 1        top row: only ever move right
paths[r][0] = 1        left column: only ever move down

"How did I get here?" is the question that generates the recurrence in most grid DP. Asking "where do I go next?" gives a correct recursion too, but it tends to produce a top-down solution with an awkward base case, and the interviewer usually wants to see the table.

m = 3, n = 7

  1  1  1  1  1  1  1
  1  2  3  4  5  6  7
  1  3  6 10 15 21 28

That is Pascal's triangle read on a diagonal, which is the tell for the closed form below.

Java

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1);            // the top row: one path to each cell

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                // row[c] still holds the value from the row above; row[c-1] is
                // this row, already updated. That is exactly what we need.
                row[c] += row[c - 1];
            }
        }

        return row[n - 1];
    }
}

The full m × n table is the version to write first, then compress. The compression works because the recurrence reads only the cell above and the cell to the left, so one row is enough — as long as you sweep left to right, which is what makes row[c-1] already the current row while row[c] is still the previous one.

Say that overlap out loud. "One array, and the read happens before the write" is the whole trick, and it is the same trick behind the 1-D knapsack.

Python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n

        for _ in range(m - 1):
            for c in range(1, n):
                row[c] += row[c - 1]

        return row[-1]

The row index is never used, so _ says so. It is a small thing, but a loop variable that is not read is a question the reader has to answer, and naming it _ answers it.

The closed form

Every path is exactly m - 1 downs and n - 1 rights in some order — the robot never moves up or left, so the multiset of moves is fixed and only the arrangement varies. Counting arrangements of a fixed multiset is a binomial coefficient:

answer = C(m + n - 2, m - 1)

That is O(min(m, n)) time and O(1) space, better than the DP on both counts. Mention it — spotting that a counting problem is combinatorial is a real signal — but be honest about why it is a footnote rather than the answer: it evaporates the instant the grid gains an obstacle, and the very next problem adds one. The DP survives that; the formula does not.

If you do write it, multiply and divide alternately (result = result * i / k as you go) rather than computing factorials, which overflow long before the answer does.

Complexity

Approach	Time	Space
Plain recursion	`O(2^(m+n))`	`O(m + n)` stack
Full DP table	`O(m · n)`	`O(m · n)`
One rolling row	`O(m · n)`	`O(n)`
Binomial coefficient	`O(min(m, n))`	`O(1)`

Roll the shorter dimension if you want O(min(m, n)) space — swap m and n when n > m, since the answer is symmetric. Worth one sentence, not five.

The pattern

Unique Paths II (63) adds obstacles, which turns one line of the recurrence into a guard. Minimum Path Sum (64) swaps the + for a min and stops being a counting problem. Climbing Stairs (70) is the same "how did I get here?" reasoning in one dimension. Together they are the four corners of introductory DP, and the fact that one recurrence stretches over all of them is the point.

What the interviewer is checking

That you derive the recurrence from "what was the last move?" rather than recall it.
That you can say why the two sets of paths do not overlap, so addition is correct.
The base cases — the top row and left column are all 1, not 0.
That you compress to one row and can explain why the sweep direction makes it work.
m = 1 or n = 1, which must return 1.
That you notice the combinatorial closed form and know why it is fragile.