Unique Paths

Approach Summary

dp[i][j] = paths from (0,0) to (i,j) = dp[i-1][j] + dp[i][j-1]. Row/column of 1s are base cases. Space-optimized to O(n).

Full Solution & Approach

A robot at (i, j) can only arrive from above or from the left, so the number of paths to a cell is the sum of the paths to those two predecessors: dp[i][j] = dp[i-1][j] + dp[i][j-1]. The top row and left column are all 1 — there is exactly one way to traverse along the edge. Filling the grid row by row gives the answer at dp[m-1][n-1]. The table only ever needs the previous row, so the full grid can be collapsed into a single row array updated left to right: dp[j] = dp[j] + dp[j-1] each step, where dp[j] holds the value from the previous row before the update. This O(n) space version is the standard optimization and avoids allocating m × n. The combinatorial formula (m+n-2 choose m-1) also works but risks overflow for large grids.

Each cell is computed once — O(m × n) time. The rolling-row version uses O(n) space instead of O(m × n).

Solution Code

Solution

def unique_paths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[-1]

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1];
    }
  }
  return row[n - 1];
}

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

int uniquePaths(int m, int n) {
    vector<int> row(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            row[j] += row[j - 1];
        }
    }
    return row[n - 1];
}

Edge Cases to Watch

Single row or column — exactly one path
1×1 grid — one path
Large grids — the rolling row avoids memory blow-up

How to Recognize This Pattern

Grid path counting
Only move right or down

Complexity Analysis

Time Complexity

O(m × n)

Space Complexity

O(n)