Unique Paths

The problem

A robot stands in the top left cell of a grid with rows rows and columns columns (call them m and n). Each move takes it one cell right or one cell down. Return how many different routes take it to the bottom right cell.

Example 1

Input: rows = 3, columns = 4

Output: 10

Every route makes 3 moves right and 2 moves down, in some order. There are 10 such orders.

	0	1	2	3
0	start
1
2				end

Example 2

Input: rows = 1, columns = 5

Output: 1

A single row: the only route is straight right.

Example 3

Input: rows = 3, columns = 3

Output: 6

2 rights and 2 downs, in 6 orders.

Constraints

• 1 ≤ m, n ≤ 100
• The answer is at most 2 × 10⁹.

Clarifying questions

Can the robot move up or left?

No. Only right and down, so it can never revisit a cell.

Are there blocked cells?

No. (Unique Paths II adds obstacles.)

What if the grid is a single cell?

Then the robot is already there: 1 route, making no moves.

Spot the pattern

Look at the last move into a cell. It came from the cell above or the cell to the left, never both. So the routes into a cell are the routes into those two cells added together. Each answer is built from smaller answers that are shared by many cells: dynamic programming on a grid.

Solutions

Grid tableO(m × n)One rowO(m × n)

Show all

There is no brute force tab. Following every route one by one takes as many steps as there are routes, up to 2 billion. A counting formula, choosing which moves go down, also works, but needs care with overflow.

Grid table O(m × n)

The idea

Make a table paths the size of the grid, where paths[row][column] counts the routes to cell (row, column).

• Every cell in the top row has 1 route: straight right. Every cell in the left column has 1 route: straight down.
• Every other cell: paths[row][column] = paths[row - 1][column] + paths[row][column - 1].

Fill it row by row, left to right. The answer is in the bottom right cell.

Why it is correct: every route into (r, c) ends with exactly one move, down from the cell above or right from the cell to the left. Those two groups do not overlap and together hold every route.

Walkthrough

	0	1	2	3
0
1
2

1. paths = rows × columns grid, top row and left column set to 1
2. for row in 1 .. rows - 1:
3. for column in 1 .. columns - 1:
4. paths[row][column] = paths[row - 1][column] + paths[row][column - 1]
5. return paths[rows - 1][columns - 1]

The robot starts at the top left and may only move right or down, to the bottom right. paths[r][c] will count the routes to cell (r, c).

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Table: paths[r][c] counts the routes to cell (r, c). The last move came from
    // above or from the left, so add those two. Every cell once: O(m × n) time and space.
    public int uniquePaths(int rows, int columns) {
        int[][] paths = new int[rows][columns];
        // The top row and left column can only be reached in a straight line.
        for (int[] row : paths) java.util.Arrays.fill(row, 1);
        for (int row = 1; row < rows; row++) {
            for (int column = 1; column < columns; column++) {
                paths[row][column] = paths[row - 1][column] + paths[row][column - 1];
            }
        }
        return paths[rows - 1][columns - 1];
    }
}

Big O

Time O(m × n)Space O(m × n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Setting up the table writes each of the m × n cells once. Then the inner loop does one addition per run. Each is a fixed job, so 1 step.

   1. paths = rows × columns grid, top row and left column set to 1
   2. for row in 1 .. rows - 1:
   3. for column in 1 .. columns - 1:
   4. paths[row][column] = paths[row - 1][column] + paths[row][column - 1]
   5. return paths[rows - 1][columns - 1]

2. 2 Count the runs on Example 1

   The table has one column per row that is summed. Rows 1 and 2 each sum 3 cells.

   12 cells set + 3 + 3 = 18 steps.

   row	1	2
   inner runs	3	3

   total

   12 cells set + 6 sums = 18

3. 3 Write the count for any n

   m × n + (m − 1) × (n − 1) steps

   Check it with Example 1: 12 + 2 × 3 = 18. That matches the count.

4. 4 Keep only the part that grows fastest

   (m − 1) × (n − 1) is less than m × n, so the total is less than 2 × m × n. Drop the 2. What is left is m × n: one visit per cell.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   The table holds m × n numbers. So the space is O(m × n).

   paths grid (m × n)

One row O(m × n)

The idea

A cell only reads the cell above it and the cell to its left. So the table never needs more than one row.

Keep a single array paths, all 1s, for the top row. For each next grid row, walk left to right and do paths[column] += paths[column - 1]. Before the write, paths[column] still holds the value from the row above. And paths[column - 1] was just updated, so it is the cell to the left in the current row. paths[0] stays 1, like the left column.

Why it is correct: it performs the same additions as the full table, in the same order. The values it overwrites are never needed again.

Walkthrough

paths

10111213

grid row

0

1. paths = [1] * columns
2. for row in 1 .. rows - 1:
3. for column in 1 .. columns - 1:
4. paths[column] += paths[column - 1]
5. return paths[columns - 1]

Each cell needs only the cell above and the cell to its left. So one row is enough: before a cell is updated, it still holds the value from the row above.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // One row: each row only needs the row above it, so update a single row in
    // place, left to right. O(m × n) time, O(n) space.
    public int uniquePaths(int rows, int columns) {
        int[] paths = new int[columns];
        java.util.Arrays.fill(paths, 1);
        for (int row = 1; row < rows; row++) {
            for (int column = 1; column < columns; column++) {
                // Before the write, paths[column] still holds the cell above;
                // paths[column - 1] is already the cell to the left.
                paths[column] += paths[column - 1];
            }
        }
        return paths[columns - 1];
    }
}

Big O

Time O(m × n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Setting up the row writes n numbers. The inner loop does one addition per run. Each is a fixed job, so 1 step.

   1. paths = [1] * columns
   2. for row in 1 .. rows - 1:
   3. for column in 1 .. columns - 1:
   4. paths[column] += paths[column - 1]
   5. return paths[columns - 1]

2. 2 Count the runs on Example 1

   Rows 1 and 2 each update 3 cells.

   4 set + 3 + 3 = 10 steps.

   row	1	2
   inner runs	3	3

   total

   4 set + 6 sums = 10

3. 3 Write the count for any n

   n + (m − 1) × (n − 1) steps

   Check it with Example 1: 4 + 2 × 3 = 10. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the lone n and the − 1s. What is left is m × n. The time is the same as the grid table.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   One row of n numbers. So the space is O(n). Swapping m and n, if n is the bigger one, brings it down to O(min(m, n)).

   paths (n)

Common mistake

Starting the inner loop at column 0

paths[0] must stay 1: the left column has only one route. Starting at column 0 reads paths[-1], which is out of bounds in most languages, and in Python silently reads the last cell.

Tested at the limits

2,000 random grids from 1 x 1 to 12 x 12, with many thin grids of one row or one column. The grid table and the one row gave the same answer every time, and matched a counting formula written in the test.

Largest inputs	Result
100 x 7 and 7 x 100, the largest grids whose answer fits the 2 × 10⁹ limit. One row.	Under 0.001 s, and under 0.01 MB of extra memory: one row of counts.
100 x 7. Grid table.	Under 0.001 s, and about 0.02 MB: the full table of 700 counts. The one row gives the same answer with a fraction of the memory.