☕ DSA Java Articles

Topics › Dynamic Programming › 2D/3D DP and DP on Grids

Grid unique paths

Medium TUF ID 297 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A robot stands on the top-left cell of an m × n grid (m rows, n columns) and wants to reach the bottom-right cell. In one move it may step one cell right or one cell down. It can never move up, move left, or leave the grid. Return the number of distinct paths from the start to the goal.

Constraints: 1 ≤ m, n ≤ 100, and the inputs are chosen so that the answer fits in a 32-bit signed integer (at most 2 × 10^9).

Example 1

m = 3, n = 7
answer = 28

Example 2

m = 3, n = 2
answer = 3          // Down-Down-Right, Down-Right-Down, Right-Down-Down

Example 3

m = 1, n = 1
answer = 1          // the robot already stands on the goal: the empty path counts once

Approach 1: Brute force, recursion on the last move

Intuition. Think about the very last move of any path that ends at cell (r, c). It came either from the cell above, (r - 1, c), or from the cell to the left, (r, c - 1). Those two groups of paths never overlap (their last moves differ), and together they cover every path. So

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

The base case is the first row and the first column. A cell in row 0 can only be reached by moving right the whole way, and a cell in column 0 only by moving down the whole way, so each has exactly one path. The answer is paths(m - 1, n - 1).

Algorithm.

  1. Call countFrom(m - 1, n - 1).
  2. In countFrom(r, c): if r == 0 or c == 0, return 1.
  3. Otherwise return countFrom(r - 1, c) + countFrom(r, c - 1).
static int bruteForce(int m, int n) {
    return countFrom(m - 1, n - 1);
}

static int countFrom(int r, int c) {
    if (r == 0 || c == 0) return 1;              // first row or first column: one straight path
    return countFrom(r - 1, c) + countFrom(r, c - 1);
}

Complexity. Time is exponential. Every leaf of the recursion tree returns 1 and the answer is the sum of the leaves, so the tree has exactly answer leaves and fewer than 2 × answer calls in total. For m = n that is about 4^n / √n calls; the 23 × 12 grid already needs roughly 4 × 10^8 calls. Space O(m + n): the depth of the recursion, because each call reduces r + c by one.

The waste is easy to see: countFrom(1, 1) is reached from countFrom(2, 1) and from countFrom(1, 2), and the same repetition happens at every interior cell. There are only m × n different questions, but we answer them over and over.

Approach 2: Memoization

Intuition. The value of countFrom(r, c) depends only on r and c, never on how we arrived there. So the first time we compute it we store it in memo[r][c], and every later call returns the stored value immediately. This turns the exponential tree into at most m × n real computations.

We use 0 as the “not computed yet” marker. That is safe because every cell of the grid has at least one path to it, so no genuine answer is 0.

Algorithm.

  1. Allocate memo[m][n] filled with 0.
  2. In countFromMemo(r, c): if r == 0 or c == 0, return 1.
  3. If memo[r][c] != 0, return it.
  4. Otherwise compute the sum of the two neighbours, store it in memo[r][c], and return it.
static int memoized(int m, int n) {
    int[][] memo = new int[m][n];                // 0 means "not computed yet"; real answers are >= 1
    return countFromMemo(m - 1, n - 1, memo);
}

static int countFromMemo(int r, int c, int[][] memo) {
    if (r == 0 || c == 0) return 1;
    if (memo[r][c] != 0) return memo[r][c];
    return memo[r][c] = countFromMemo(r - 1, c, memo) + countFromMemo(r, c - 1, memo);
}

Complexity. Time O(m × n): each cell is computed once, in constant time apart from its two recursive lookups. Space O(m × n) for the table plus O(m + n) for the call stack.

Approach 3: Tabulation with one row

Intuition. Memoization fills the table in whatever order the recursion happens to reach it. We can instead fill it ourselves, row by row from the top, because every cell only needs the cell above it and the cell to its left, and both are already final when we reach it. That removes the recursion entirely.

Even the full table is more than we need. Row r only reads row r - 1. If we keep a single array row and update it left to right, then at the moment we update row[c]:

So row[c] += row[c - 1] is exactly the recurrence. Column 0 is never updated and stays 1, which is the first-column base case.

Algorithm.

  1. Create row of length n filled with 1 (the first row).
  2. For each row r from 1 to m - 1, and each column c from 1 to n - 1, do row[c] += row[c - 1].
  3. Return row[n - 1].
static int tabulation(int m, int n) {
    int[] row = new int[n];
    Arrays.fill(row, 1);                         // first row: exactly one way to reach each cell
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            row[c] += row[c - 1];                // old row[c] = from above, row[c - 1] = from the left
        }
    }
    return row[n - 1];
}

Dry run on m = 3, n = 7:

after row row contents
0 1 1 1 1 1 1 1
1 1 2 3 4 5 6 7
2 1 3 6 10 15 21 28

The answer is row[6] = 28. Notice the numbers: they are entries of Pascal’s triangle. That is the hint for the final approach.

Complexity. Time O(m × n). Space O(n). If n is much larger than m, swapping the two arguments first gives O(min(m, n)) space, since the answer is symmetric.

Approach 4: Optimal, combinatorics

Intuition. Forget the grid and look at the sequence of moves. Every path from the top-left to the bottom-right makes exactly m - 1 down moves and n - 1 right moves, m + n - 2 moves in total, just in some order. Conversely, any ordering of those moves is a valid path: the robot can never fall off the grid, because it never makes more than m - 1 downs or n - 1 rights. So paths and orderings are in one-to-one correspondence, and the number of orderings is the number of ways to choose which of the m + n - 2 positions hold the down moves:

answer = C(m + n - 2, m - 1) = C(m + n - 2, n - 1).

To compute it cheaply, we choose positions for the rarer move, k = min(m - 1, n - 1), and build the binomial coefficient incrementally:

C(total - k + i, i) = C(total - k + i - 1, i - 1) × (total - k + i) / i.

After step i the variable ways equals C(total - k + i, i), an integer, so the product before the division is always a multiple of i and the division is exact. The order matters: multiply first, then divide. Dividing first would truncate.

Algorithm.

  1. Let total = m + n - 2 and k = min(m - 1, n - 1).
  2. Start with ways = 1 (a long).
  3. For i from 1 to k: ways = ways × (total - k + i) / i.
  4. Return ways as an int.
static int optimal(int m, int n) {
    int total = m + n - 2;                       // every path has exactly this many moves
    int k = Math.min(m - 1, n - 1);              // pick positions for the rarer kind of move
    long ways = 1;
    for (int i = 1; i <= k; i++) {
        ways = ways * (total - k + i) / i;       // now ways == C(total - k + i, i), always an integer
    }
    return (int) ways;
}

Dry run on m = 3, n = 7: total = 8, k = 2.

i ways before multiply by divide by ways after
1 1 7 1 7 = C(7, 1)
2 7 8 2 28 = C(8, 2)

Complexity. Time O(min(m, n)): one multiplication and one division per step. Space O(1).

Why long? The running value C(total - k + i, i) only grows with i, so it never exceeds the final answer, but the product ways × (total - k + i) briefly does. For the 51 × 9 grid the last step multiplies C(57, 7) = 264,385,836 by 58, about 1.5 × 10^10, which overflows int even though the final answer 1,916,797,311 fits. In long the product stays below 2 × 10^9 × 200, far from the limit.

Edge cases and pitfalls