Unique Paths

Medium Problem 127 of 151 Java and Python

Problem

A robot starts at the top-left corner of an m × n grid and can only move right or down. How many different paths reach the bottom-right corner?

Example 1

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

Example 2

Input: m = 3, n = 2
Output: 3
Why: Right-Down-Down, Down-Down-Right, Down-Right-Down.

Constraints

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

Explanation

You reach a cell either from the cell above or the cell to the left, so paths(r, c) = paths(r - 1, c) + paths(r, c - 1). Cells in the first row or column have exactly one path.

Each row only needs the row above, so one array updated left to right is enough.

Approach 1 · Naive

Plain recursion

Time O(2^(m + n))
Space O(m + n) recursion

Count paths to a cell as the sum of paths to the cell above and the cell to the left.

paths(r, c) = 1 when r == 0 or c == 0.
Otherwise paths(r - 1, c) + paths(r, c - 1).

Java

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

Python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

Approach 2 · Optimal

DP with one row

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

Keep one row of path counts. Moving down a row, each cell becomes "itself (from above) + its left neighbour".

row = [1] * n.
For each of the remaining m - 1 rows, for c from 1: row[c] += row[c - 1].
Return row[n - 1].

Java

import java.util.*;

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1);
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1];
            }
        }
        return row[n - 1];
    }
}

Python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n
        for _ in range(1, m):
            for c in range(1, n):
                row[c] += row[c - 1]
        return row[-1]

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2^(m + n))	O(m + n) recursion
Optimal DP with one row	O(m · n)	O(n)

Key takeaways

The answer is also the binomial coefficient C(m + n – 2, m – 1): choose which of the moves go down.
Unique Paths II adds obstacles: set blocked cells to 0 in the same loop.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem