Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Unique Paths

Unique Paths explained: count grid routes moving only right or down with a 2D DP table, the 1D space trick and the combinatorics formula, with tested Python.

Also searched as: unique paths in a grid dp · number of paths from top-left to bottom-right · grid paths moving right or down

🧮

Try it live Free

2D DP Table: LCS & Edit Distance

The DP Table lab fills a 2D grid cell by cell from its up, left and diagonal neighbours for LCS; Unique Paths fills a grid the same way, adding the up and left neighbours.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

A robot starts at the top-left cell of an m × n grid and wants to reach the bottom-right cell. It may only move right or down one cell at a time. Count the number of distinct routes.

Inputm = 3, n = 7
Output28
Inputm = 3, n = 2
Output3

right-down-down, down-right-down, down-down-right

The key insight

The only ways into a cell are from the cell above or the cell to the left. So paths[i][j] = paths[i-1][j] + paths[i][j-1], and every cell in the first row or column has exactly one path. Filling row by row, you only need one row of numbers.

Brute force first: Recursively exploring every route makes about C(m+n-2, m-1) calls, which grows exponentially.

Step-by-step approach

  1. Create a row row of n ones (the first row: only rightward moves).
  2. For each of the remaining m - 1 rows, sweep j from 1 to n - 1.
  3. Update row[j] += row[j - 1]: the old row[j] is the cell above, row[j - 1] is the cell to the left.
  4. Return row[-1].

Python solution

PYTHON 3tested
def unique_paths(m, n):
    row = [1] * n                     # first row: one path to each cell
    for _ in range(m - 1):
        for j in range(1, n):
            row[j] += row[j - 1]      # from above (old row[j]) + from left
    return row[-1]

Complexity

TimeO(m · n)
SpaceO(n)

Each grid cell is computed once in O(1). Keeping one row is enough because each cell only needs the cell above and the cell to its left.

Common mistakes

Frequently asked questions

What is the time and space complexity of Unique Paths?

O(m × n) time and O(n) space with the rolling row. The combinatorics formula is O(min(m, n)) time.

Is there a formula for Unique Paths?

Yes. Every route is a sequence of m - 1 downs and n - 1 rights, so the count is the binomial coefficient C(m + n - 2, m - 1).

How do obstacles change the solution?

Set the count of any obstacle cell to 0 and keep the same recurrence. Be careful with the first row and column: after an obstacle, the cells beyond it are unreachable.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.