Unique Paths

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

A robot sits in the top-left cell of a grid with m rows and n columns and wants to reach the bottom-right cell. Each move takes it exactly one cell to the right or one cell down; it can never move left, up or diagonally. Return the number of different paths from the start to the finish. Two paths are different if they differ in at least one move. On a 1 x 1 grid the robot is already there, which counts as one path.

Examples

m = 3, n = 7 returns 28

One of the 28 paths: 6 moves right and 2 moves down.

Every path makes exactly 6 moves right and 2 moves down, 8 moves in all. Paths differ only in where the 2 down moves fall among those 8, and there are 28 ways to place them.

m = 3, n = 2 returns 3

The three paths are right then down twice, down then right then down, and down twice then right.

Constraints

1 <= m, n <= 100
The answer is at most 2 * 10^9.

Hints

Hint 1

Think about the last move into any cell. Where could the robot have been one step earlier?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

The robot enters any cell from the cell above it or the cell to its left, so paths(r, c) = paths(r-1, c) + paths(r, c-1), and every cell in the top row and left column has exactly 1 path. Filling row by row, one array of length n is enough: row[c] += row[c-1] adds the left neighbor to the count carried down from above. O(m * n) time, O(n) space. The closed form C(m+n-2, m-1) also works.

Time

O(m * n)

Space

O(n)

Pitfall

Seeding the top row and left column with 0 instead of 1. There's exactly one straight-line way to reach each edge cell, and zero seeds make every sum 0. With the closed form, computing full factorials overflows a 32-bit int.

Solutions

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1); // top row: one path to each cell
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1]; // from above (old row[c]) + from the left
            }
        }
        return row[n - 1];
    }
}

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n  # top row: one path to each cell
        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]