Unique Paths — Solution

Problem

You have a robot sitting at the top-left corner of an m×n grid. The robot can only move right or down. Count how many distinct paths exist from the top-left to the bottom-right corner.

• Input: m = 3, n = 7
• Output: 28
• Explanation: With 3 rows and 7 columns, there are exactly 28 distinct right-down paths from corner to corner.

If m = 3, n = 2 to see a smaller case: every path must take exactly 1 step down and 1 step right (in some order), giving just 3 paths.

Intuition

Every single path from top-left to bottom-right makes exactly (m−1) down moves and (n−1) right moves — the total number of steps is fixed, only the order varies. You can either count directly using combinatorics, or build up the answer cell by cell: the number of paths reaching any cell equals the paths arriving from above plus the paths arriving from the left, since those are the only two ways to enter it.

Approach 1 — Dynamic Programming

Maintain a single row of counts and update it in-place. Before processing row i, row[j] holds the number of paths to reach row i−1, column j (from above). After updating left-to-right, row[j] accumulates the left-neighbor's count too, giving the correct total for row i.

1. Initialize an array of length n filled with 1s — every cell in the first row has exactly one path (keep moving right).
2. For each subsequent row, leave row[0] untouched (left column is always 1 — only path is straight down).
3. For columns 1 through n−1, set row[j] += row[j-1] — adds left-neighbor paths to the already-stored above-paths.
4. Repeat for all m−1 remaining rows.
5. Return row[n-1].

1def uniquePaths(self, m: int, n: int) -> int:
2    row = [1] * n  # first row: exactly one path to each cell
3
4    for _ in range(1, m):
5        for col in range(1, n):
6            row[col] += row[col - 1]  # row[col] still holds above-count; add left-count
7
8    return row[n - 1]

Time: O(m × n) — visits every cell exactly once.
Space: O(n) — one row of counts reused for each of the m rows.

Approach 2 — Math (Combinatorics)

Every path consists of exactly (m−1) down steps and (n−1) right steps, totaling (m+n−2) moves. Counting distinct paths is identical to choosing which (m−1) of those moves are the down steps: C(m+n−2, m−1).

1. Compute total steps: steps = m + n - 2.
2. Choose the smaller of (m−1) and (n−1) as k to minimize loop iterations.
3. Compute C(steps, k) iteratively: multiply by (steps - i) and divide by (i + 1) at each step to stay integer-valued and avoid overflow.
4. Return the result.

1from math import comb
2
3def uniquePaths(self, m: int, n: int) -> int:
4    # choose which (m-1) of the (m+n-2) total moves are downward steps
5    return comb(m + n - 2, m - 1)

Time: O(min(m, n)) — loop runs at most min(m−1, n−1) iterations.
Space: O(1) — only a handful of scalar variables.

Complexity Summary

Common Mistakes

• Forgetting to initialize the first row to all 1s — the base case is that every cell in the top row (and left column) has exactly one path; initializing with zeros forces you to fill them separately and is easy to get wrong.
• Starting the inner loop at col = 0 — row[0] must stay 1 throughout (left column always has one path), so the update loop must begin at column 1.
• Using factorial for the combinatorics approach — computing factorial(m+n-2) // factorial(m-1) // factorial(n-1) creates a huge intermediate value before dividing; the iterative formulation multiplies and divides in lockstep, keeping the running total small and integer-valued at every step.
• Assuming the answer changes when you swap m and n — C(m+n−2, m−1) = C(m+n−2, n−1), so the answer is symmetric; swapping rows and columns gives the same count, which is correct mathematically but can mask a bug in problems that extend this grid (like Unique Paths II).
• Applying the math formula when there are blocked cells — the combinatorics approach counts all orderings of moves, which only works on an empty grid; any obstacle invalidates it and requires the DP approach.

Related Problems

• unique-paths-ii — same grid traversal but with obstacles; forces the DP approach
• minimum-path-sum — find the minimum-cost path using the identical cell recurrence
• triangle — similar row-by-row DP on a triangular structure
• climbing-stairs — the 1D version of this recurrence (ways to reach step n)
• coin-change — another classic count-paths-to-target DP problem