#59 · 2D DP

Unique Paths

A robot starts at the top-left of an m × n grid and may move only right or down. How many distinct paths lead to the bottom-right corner?

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Two-dimensional DP table

dp[r][c] = the number of paths to cell (r, c). A cell is reached either from above or from the left, so dp[r][c] = dp[r − 1][c] + dp[r][c − 1]. The first row and column have one path each.

Memory layout

An m × n integer grid stored row by row.

Operation	Cost
time	O(m·n)
space	O(m·n); O(n) with one rolling row

Rolling row

A cell reads only the cell above (the old value of the same array slot) and the cell to its left (already updated). One array updated in place from left to right therefore holds each row in turn.

Memory layout

A flat array of n integers.

Operation	Cost
space	O(n)

Why it fits

The last move into any cell is either down or right, so the count for a cell is the sum of two smaller counts: a textbook additive recurrence.
The same cell is a sub-problem of many larger ones, so storing counts turns an exponential recursion into one visit per cell.
Each row depends only on the previous row, so the 2-D table collapses to a single array.

Why alternatives degrade

Enumerating every path:: The number of paths is itself the answer (C(m + n − 2, m − 1)), which grows exponentially; listing them is infeasible.
Greedy:: There is nothing to maximise; every path counts equally.
Plain recursion:: It recomputes the same cells repeatedly and takes time proportional to the answer.

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(2^(m+n))space O(m + n) recursion

paths(r, c) = paths(r − 1, c) + paths(r, c − 1); any cell in the top row or left column has exactly one path.

int uniquePaths(int m, int n) {
    function<int(int, int)> paths = [&](int r, int c) -> int {
        if (r == 0 || c == 0) return 1;
        return paths(r - 1, c) + paths(r, c - 1);
    };
    return paths(m - 1, n - 1);
}

public int uniquePaths(int m, int n) {
    return paths(m - 1, n - 1);
}
private int paths(int r, int c) {
    if (r == 0 || c == 0) return 1;
    return paths(r - 1, c) + paths(r, c - 1);
}

def unique_paths(m, n):
    def paths(r, c):
        if r == 0 or c == 0: return 1
        return paths(r - 1, c) + paths(r, c - 1)
    return paths(m - 1, n - 1)

function uniquePaths(m: number, n: number): number {
  const paths = (r: number, c: number): number => {
    if (r === 0 || c === 0) return 1;
    return paths(r - 1, c) + paths(r, c - 1);
  };
  return paths(m - 1, n - 1);
}

Flaws & bottlenecks

The same cell is recomputed many times.
The number of calls is about twice the answer, which grows exponentially with the grid size.
Recursion depth m + n.

Interviewer cross-questions

Why is the base case the top row and left column?

Say: From the start you can only reach those cells by moving purely right or purely down, so there is exactly one path to each.

How many calls does it make?

Say: Roughly twice the number of paths (every leaf contributes 1 to the answer), so it is proportional to C(m + n − 2, m − 1).

What fixes it?

Say: Memoise paths(r, c) so every cell is computed once.

2 · intermediate

Memoised recursion

time O(m·n)space O(m·n)

Cache each cell's count in a map keyed by r × n + c. A repeated request returns the stored count without recursing.

int uniquePaths(int m, int n) {
    unordered_map<int, int> memo;
    function<int(int, int)> paths = [&](int r, int c) -> int {
        if (r == 0 || c == 0) return 1;
        int key = r * n + c;
        auto known = memo.find(key);
        if (known != memo.end()) return known->second;
        int result = paths(r - 1, c) + paths(r, c - 1);
        memo[key] = result;
        return result;
    };
    return paths(m - 1, n - 1);
}

public int uniquePaths(int m, int n) {
    Map<Integer, Integer> memo = new HashMap<>();
    return paths(m - 1, n - 1, n, memo);
}
private int paths(int r, int c, int n, Map<Integer, Integer> memo) {
    if (r == 0 || c == 0) return 1;
    int key = r * n + c;
    Integer known = memo.get(key);
    if (known != null) return known;
    int result = paths(r - 1, c, n, memo) + paths(r, c - 1, n, memo);
    memo.put(key, result);
    return result;
}

def unique_paths(m, n):
    memo = {}
    def paths(r, c):
        if r == 0 or c == 0: return 1
        key = r * n + c
        known = memo.get(key)
        if known is not None: return known
        result = paths(r - 1, c) + paths(r, c - 1)
        memo[key] = result
        return result
    return paths(m - 1, n - 1)

function uniquePaths(m: number, n: number): number {
  const memo = new Map<number, number>();
  const paths = (r: number, c: number): number => {
    if (r === 0 || c === 0) return 1;
    const key = r * n + c;
    const known = memo.get(key);
    if (known !== undefined) return known;
    const result = paths(r - 1, c) + paths(r, c - 1);
    memo.set(key, result);
    return result;
  };
  return paths(m - 1, n - 1);
}

Flaws & bottlenecks

Still recursive: depth m + n.
Hash-map overhead for a dense grid.
Building a numeric key r × n + c is easy to get wrong (it must use the same n everywhere).

Interviewer cross-questions

Why a numeric key instead of a string?

Say: It avoids allocating and hashing a string for every cell. r × n + c is unique for every cell of an m × n grid.

What is the complexity?

Say: Each of the m·n cells is computed once, and every later request is a lookup: O(m·n).

How would you avoid recursion?

Say: Fill the table row by row, which also makes the dependencies explicit.

3 · advanced

2-D table, row by row

time O(m·n)space O(m·n)

Create an m × n table of ones. For each cell not on the first row or column set dp[r][c] = dp[r − 1][c] + dp[r][c − 1]. The answer is the bottom-right cell.

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }
    return dp[m - 1][n - 1];
}

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

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({ length: m }, () => new Array<number>(n).fill(1));
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }
  return dp[m - 1][n - 1];
}

Flaws & bottlenecks

Stores the whole grid although only the previous row is ever needed.
For very large grids the answer overflows 32-bit integers (the problem guarantees it fits).
Initialising everything to 1 is a trick that hides the edge cases; it is easy to forget why it works.

Interviewer cross-questions

Why initialise the whole table to 1?

Say: The first row and column should be 1, and every other cell is overwritten before it is read, so a table of ones is correct and needs no special-case loops.

Is there a closed-form answer?

Say: Yes: every path has m − 1 downs and n − 1 rights in some order, so the count is C(m + n − 2, m − 1). It can be computed in O(min(m, n)) time.

How can the memory be reduced?

Say: Keep a single row: each cell needs only the value above (the old value in the same slot) and the value to its left (just updated).

4 · expert

One rolling row

time O(m·n)space O(n)

Keep a single array of n ones. For each further row update it left to right with row[c] += row[c − 1]: row[c] (before the update) is the value from above and row[c − 1] (already updated) is the value from the left.

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

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];
}

def unique_paths(m, n):
    row = [1] * n
    for r in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[n - 1]

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

Flaws & bottlenecks

The in-place update relies on the iteration order: going right to left would give wrong answers.
The old values of earlier rows are lost, so you cannot reconstruct paths.
Choosing the shorter dimension as the array length would halve the memory again; this version does not.

Interviewer cross-questions

Why does the update order matter?

Say: Going left to right, row[c − 1] already holds the current row's value while row[c] still holds the previous row's. That is exactly "from the left" and "from above".

Can you use even less memory?

Say: Yes: make the array as long as the shorter side, or use the closed form C(m + n − 2, m − 1), computed with an exact multiplicative loop in O(min(m, n)) time and O(1) space.

What if some cells are blocked?

Say: Set the blocked cells to 0 in the array as you reach them (row[c] = 0). The same rolling update then counts only valid paths (Unique Paths II).

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

int uniquePaths(int m, int n) {
    function<int(int, int)> paths = [&](int r, int c) -> int {
        if (r == 0 || c == 0) return 1;
        return paths(r - 1, c) + paths(r, c - 1);
    };
    return paths(m - 1, n - 1);
}

public int uniquePaths(int m, int n) {
    return paths(m - 1, n - 1);
}
private int paths(int r, int c) {
    if (r == 0 || c == 0) return 1;
    return paths(r - 1, c) + paths(r, c - 1);
}

def unique_paths(m, n):
    def paths(r, c):
        if r == 0 or c == 0: return 1
        return paths(r - 1, c) + paths(r, c - 1)
    return paths(m - 1, n - 1)

function uniquePaths(m: number, n: number): number {
  const paths = (r: number, c: number): number => {
    if (r === 0 || c === 0) return 1;
    return paths(r - 1, c) + paths(r, c - 1);
  };
  return paths(m - 1, n - 1);
}

int uniquePaths(int m, int n) {
    unordered_map<int, int> memo;
    function<int(int, int)> paths = [&](int r, int c) -> int {
        if (r == 0 || c == 0) return 1;
        int key = r * n + c;
        auto known = memo.find(key);
        if (known != memo.end()) return known->second;
        int result = paths(r - 1, c) + paths(r, c - 1);
        memo[key] = result;
        return result;
    };
    return paths(m - 1, n - 1);
}

public int uniquePaths(int m, int n) {
    Map<Integer, Integer> memo = new HashMap<>();
    return paths(m - 1, n - 1, n, memo);
}
private int paths(int r, int c, int n, Map<Integer, Integer> memo) {
    if (r == 0 || c == 0) return 1;
    int key = r * n + c;
    Integer known = memo.get(key);
    if (known != null) return known;
    int result = paths(r - 1, c, n, memo) + paths(r, c - 1, n, memo);
    memo.put(key, result);
    return result;
}

def unique_paths(m, n):
    memo = {}
    def paths(r, c):
        if r == 0 or c == 0: return 1
        key = r * n + c
        known = memo.get(key)
        if known is not None: return known
        result = paths(r - 1, c) + paths(r, c - 1)
        memo[key] = result
        return result
    return paths(m - 1, n - 1)

function uniquePaths(m: number, n: number): number {
  const memo = new Map<number, number>();
  const paths = (r: number, c: number): number => {
    if (r === 0 || c === 0) return 1;
    const key = r * n + c;
    const known = memo.get(key);
    if (known !== undefined) return known;
    const result = paths(r - 1, c) + paths(r, c - 1);
    memo.set(key, result);
    return result;
  };
  return paths(m - 1, n - 1);
}

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }
    return dp[m - 1][n - 1];
}

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

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({ length: m }, () => new Array<number>(n).fill(1));
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }
  return dp[m - 1][n - 1];
}

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

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];
}

def unique_paths(m, n):
    row = [1] * n
    for r in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[n - 1]

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