Unique Paths

Examples

Input: m = 3, n = 7
Output: 28

Input: m = 3, n = 2
Output: 3

Right-Down-Down, Down-Right-Down, and Down-Down-Right.

Constraints

• 1 <= m, n <= 100

Approach

The robot can only arrive at any given cell from one of two places: the cell directly above it, or the cell directly to its left. So the number of ways to reach a cell is just the sum of the ways to reach those two neighbors.

That means you can build up a table of "ways to reach this cell," starting from the top-left (1 way: don't move at all) and filling in each row left to right, top to bottom, using only values you've already computed.

Solutions

Brute Force — Recursion

From any cell, recursively add the number of paths from moving right and the number of paths from moving down. Correct, but recomputes the same cells many times over.

function uniquePaths(m, n) {
  function countFrom(row, col) {
    if (row === m - 1 || col === n - 1) return 1;
    return countFrom(row + 1, col) + countFrom(row, col + 1);
  }
  return countFrom(0, 0);
}

Time: O(2^(m+n)) · Space: O(m + n) — recursion depth

Optimal — Bottom-Up 2D Table

Build a grid where each cell holds the number of ways to reach it, filling in the first row and column as 1 (only one way to reach any edge cell), then every other cell as the sum of the cell above and the cell to the left.

function uniquePaths(m, n) {
  const table = Array.from({ length: m }, () => new Array(n).fill(1));

  for (let row = 1; row < m; row++) {
    for (let col = 1; col < n; col++) {
      table[row][col] = table[row - 1][col] + table[row][col - 1];
    }
  }

  return table[m - 1][n - 1];
}

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