Unique Paths

A robot stands on the top-left cell of a grid with m rows and n columns. It wants to reach the bottom-right cell, and on each move it may step exactly one cell right or one cell down. It can never move left, up or off the grid.

Return how many different routes lead from the top-left cell to the bottom-right cell. Two routes are different if their sequences of moves differ.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 100
• The answer is at most 2 × 109.

Pattern Path · Dynamic Programming · problem 152 of 169

Start simple

Recursively try both moves from every cell and count the routes that reach the corner: exponential time, about O(2^m+n).

The key idea

Every route into cell (r, c) arrives either from above, (r-1, c), or from the left, (r, c-1), and those two groups of routes never overlap because their last move differs. So

paths(r, c) = paths(r-1, c) + paths(r, c-1),

with paths = 1 along the top row and left column (there is only one straight route along an edge).

The plain recursion recomputes the same cells over and over, which is why it explodes. Filling a table in reading order computes each cell once, from two values that are already known. Since a row only depends on the row above, keep one array row of length n: walking left to right, row[c] still holds the value from above, and row[c-1] already holds the new value to the left, so row[c] += row[c-1] updates it in place.

(There is also a closed form: any route is an arrangement of m-1 downs and n-1 rights, giving C(m+n-2, m-1).)

Complexity

• Time: O(m·n)
• Space: O(n)

Python

class Solution:
    def uniquePaths(self, m, n):
        # row[c] = number of routes to column c of the current row.
        row = [1] * n
        for _ in range(1, m):
            for c in range(1, n):
                row[c] += row[c - 1]  # from above (old row[c]) + from the left
        return row[-1]

JavaScript

var uniquePaths = function(m, n) {
  // row[c] = number of routes to column c of the current row.
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      row[c] += row[c - 1]; // from above (old row[c]) + from the left
    }
  }
  return row[n - 1];
};

What the interviewer is checking

A gentle introduction to grid DP: can you find the recurrence, see why naive recursion is exponential, and compress the table to one row?

Mistakes to avoid

• Plain recursion without memoisation, which times out even on modest grids.
• Wrong base cases: the whole first row and first column are 1, not just the start cell.
• Computing the binomial with full factorials in a fixed-width integer type, which overflows.

Follow-ups to expect

• Some cells are blocked by obstacles. (Set blocked cells to 0 in the DP.)
• Each cell has a cost; find the cheapest route. (Min instead of sum.)
• Can you compute it in O(min(m, n)) time? (Multiplicative binomial formula.)

In real software

Counting monotone lattice paths underlies combinatorics in probability (random walks), and the same grid recurrence drives sequence alignment and edit-distance tables in bioinformatics and diff tools.

Practice next