77. Unique Paths · DSA Practice

A robot starts at the top-left 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

Hint 1

paths(r, c) = paths(r − 1, c) + paths(r, c − 1).

Hint 2

The first row and column each have exactly one path.

Dynamic ProgrammingMath

Approach 1: 2-D DP table

Fill an m × n grid.

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

Approach 2: 1-D rolling row

Reuse one row.

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

Approach 3: Combinatorics ✅

C(m+n−2, m−1).

⏱ Time O(min(m, n))💾 Space O(1)

Reference solution for Combinatorics (time O(min(m, n)), space O(1)). Each solution passes every test in all four languages.

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

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];   // above + left
        return row[n - 1];
    }
}

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> row(n, 1);
        for (int r = 1; r < m; r++)
            for (int c = 1; c < n; c++) row[c] += row[c - 1];   // above + left
        return row[n - 1];
    }
};

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++)
    for (let c = 1; c < n; c++) row[c] += row[c - 1]; // above + left
  return row[n - 1];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (2-D).