A warehouse robot sits at receiving in the top-left cell of an m by n aisle grid. Packing is the bottom-right cell. One-way belts allow only a step right or a step down — never up, never left, never a diagonal. Ops wants the count of routes, not one path. The intern recursed every fork: from (r, c) try right, try down. A 3×3 stub returned. A 20×20 floor was still expanding route trees when the shift ended.

Unique Paths asks how many right-and-down walks reach the far corner. An array (or a grid of cells) already gives coordinates for free. Searching every walk uses that and still pays an exponential tree. You are not asked to emit a path.

This is an interview writeup, not a graph-search lecture. Here we only care that every cell is reached from the cell above or the cell to the left, so the count is a sum, not a forest.

The problem

Given positive integers m and n, a robot starts at (0, 0) on an m by n grid and may move only right or down. Return the number of distinct paths to (m - 1, n - 1). Every path visits m + n - 2 steps: exactly m - 1 downs and n - 1 rights. The grid has no obstacles.

m = 4, n = 2  →  4     three downs, one right
m = 3, n = 3  →  6
m = 1, n = 5  →  1     only rights along a single row
m = 1, n = 1  →  1     already at the destination

Note: Four-direction search is a different map. Obstacles are a different prompt (zero out a blocked cell, then the same recurrence). This board is an empty grid and two legal moves.

Recursing right or down is the honest brute force

From (r, c), if you sit on the destination that is one path. If you walk off the grid, zero. Otherwise add the two recursive calls. Correct. Exponential: most cells are reached by many overlapping prefixes, and the tree recomputes them.

int uniquePathsRec(int m, int n) {
    return from(0, 0, m, n);
}

int from(int r, int c, int m, int n) {
    if (r == m - 1 && c == n - 1) {
        return 1;
    }
    if (r >= m || c >= n) {
        return 0;
    }
    return from(r + 1, c, m, n) + from(r, c + 1, m, n);
}

At m = n = 3 this is a rounding error. At a real floor you paid a route tree for a question a table answers once per cell: paths to this cell = above + left. Memoizing from(r, c) is the same recurrence filled on demand.

Fill left-plus-above, or roll one row

Let dp[r][c] be the number of ways to reach cell (r, c) from the origin. The first row is all 1 — only rights. The first column is all 1 — only downs. Every other cell:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Walk a 3×3:

      c=0  c=1  c=2
r=0    1    1    1
r=1    1    2    3
r=2    1    3    6

Cell (1, 1) is 1 + 1. Cell (2, 2) is 3 + 3. The destination is 6.

The Java is that table. Seed the first row and first column, then fill:

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int r = 0; r < m; r++) {
        dp[r][0] = 1;
    }
    for (int c = 0; c < n; c++) {
        dp[0][c] = 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];
}

A rolling row is the same recurrence: start as a row of ones, then for each later row row[c] += row[c - 1] from c = 1. You only needed the previous row, and the left cell is already the updated value in this row.

You can also skip the table: choose which of the m + n - 2 steps are the downs — C(m + n - 2, m - 1). Multiply in a loop and divide carefully; that is combinatorics, not a DFS. Take k = min(m - 1, n - 1) so the loop is short. Overflow is the reason interviews still like the DP fill when they cap the answer in 32-bit int.

int uniquePathsComb(int m, int n) {
    int k = Math.min(m - 1, n - 1);
    int steps = m + n - 2;
    long ans = 1;
    for (int i = 1; i <= k; i++) {
        ans = ans * (steps - k + i) / i;
    }
    return (int) ans;
}

Time is O(m · n) for the table or the rolling row. Space is O(m · n) for the grid, or O(n) if you roll. Combinatorics is O(min(m, n)) multiplies if you keep a long.

Note: Do not DFS once m and n are a scan. Overlapping prefixes are the whole point of the sum. Seeding only dp[0][0] = 1 and forgetting the first row/column leaves the walls at 0 unless you also add those base cases in the inner loop.

What interviewers usually poke next

  • Rolling row. Same fill, O(n) extra. If they ask you to shrink space, do not rebuild a second algorithm — drop the unused rows.
  • Combinatorics. C(m + n - 2, m - 1). Name overflow and integer division order if you multiply ans = ans * (steps - k + i) / i. The DP fill avoids that dance when the prompt promises the answer fits in int.
  • Obstacles. Zero a blocked cell; it contributes nothing to neighbors. Same recurrence, different seed. Do not switch to a graph search unless the moves change.
  • Minimum path sum. Weights on cells, one cheapest walk. Different job. The count table does not store costs.
  • Start or moves change. Four directions, or a start other than (0, 0), is a different map. Ask before you reuse this fill.

You are done with this problem when you can fill a 3×3 to 6 on a whiteboard, say why the DFS tree is correct, and name the rolling row as the same numbers without a second idea.