medium

Unique Paths

Count how many distinct paths lead from the top-left to the bottom-right of a grid.

1. Define the problem

Unique Paths

A robot sits at the top-left corner of an m x n grid and can only move down or right. Return the number of distinct paths to reach the bottom-right corner. The number of ways to reach a cell is the ways to reach the cell above it plus the ways to reach the cell to its left , two smaller subproblems that were already solved earlier in the same pass.

Constraints

  • 1 ≤ m, n ≤ 100
  • The answer is guaranteed to fit in a 32-bit integer.

Example

Inputm = 3, n = 7
Output28

Explanation There are 28 distinct ways to move from the top-left to the bottom-right of a 3x7 grid.

2. Visualize the solution

Fill one row at a time, adding the cell above

Fill one row at a time, adding the cell above
Statusrow 0

A 3x3 grid. The first row can only be reached by moving right, so every cell starts at 1.

What happens in this step

m = 3, n = 3
dp = [1, 1, 1]

There's only one way to reach any cell along the top row: keep moving right from the start.
Step 1 of 5

Steps to visualize

  1. Start the first row with every cell equal to 1 — there is only one way to reach any cell by moving right along the top edge.
  2. For every later row, walk left to right: each cell becomes its current value (paths from the left) plus the value already sitting in that column (paths from above).
  3. After processing every row, the last cell holds the total number of distinct paths.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill one row at a time, adding the cell above
Statusrow 0

A 3x3 grid. The first row can only be reached by moving right, so every cell starts at 1.

What happens in this step

m = 3, n = 3
dp = [1, 1, 1]

There's only one way to reach any cell along the top row: keep moving right from the start.
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);

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

  return dp[n - 1];
}
Time
O(m * n)
Space
O(n)
5. Test cases

Test cases

InputExpectedCovers
m = 3, n = 728example from the docstring
m = 3, n = 23a second worked example
m = 1, n = 11smallest valid grid, a single cell
m = 1, n = 51a single row, only one straight path
m = 5, n = 11a single column, only one straight path
m = 7, n = 328a transposed grid gives the same count
m = 2, n = 22smallest non-trivial square grid

Keep reading