111.Unique Paths

Intuition

Stand at (r, c) and ask "how many ways to the goal from here?". Move right or move down and add the two counts. Walking off the grid gives 0 ways; standing on the goal gives 1 way.

Algorithm

1. Define count(r, c):
   • If r == m or c == n, return 0 (off the grid).
   • If r == m - 1 and c == n - 1, return 1 (reached the goal).
   • Return count(r + 1, c) + count(r, c + 1).
2. Return count(0, 0).

Visualization

For m = 3, n = 2 the three leaves that reach the goal give 3. Notice that (1,1) is solved twice — the overlap explodes on larger grids.

Code

class Solution {
    public int uniquePaths(int m, int n) {
        return count(0, 0, m, n);
    }

    private int count(int r, int c, int m, int n) {
        if (r == m || c == n) {
            return 0; // stepped outside the grid
        }
        if (r == m - 1 && c == n - 1) {
            return 1; // reached bottom-right
        }
        return count(r + 1, c, m, n) + count(r, c + 1, m, n);
    }
}

Complexity

• Time: O(2^(m+n)) — every call branches twice and the path length is m + n - 2.
• Space: O(m + n) — recursion depth equals the path length.

Intuition

There are only m * n distinct states (r, c). Cache each answer the first time it is computed and the exponential tree collapses to a grid of work.

Algorithm

1. Create memo[m][n] filled with 0 (every reachable answer is ≥ 1, so 0 means "not computed").
2. In count(r, c), handle the bases as before, return memo[r][c] if set, otherwise compute count(r + 1, c) + count(r, c + 1), store and return it.

Dry Run

m = 3, n = 2   memo after the call count(0,0) finishes:

        c=0  c=1
r=0  [   3    1 ]
r=1  [   2    1 ]
r=2  [   1    1 ]

memo[1][1] is computed once (value 1) and reused by (0,1) and (1,0).

Code

class Solution {
    private int[][] memo;

    public int uniquePaths(int m, int n) {
        memo = new int[m][n];
        return count(0, 0, m, n);
    }

    private int count(int r, int c, int m, int n) {
        if (r == m || c == n) {
            return 0;
        }
        if (r == m - 1 && c == n - 1) {
            return 1;
        }
        if (memo[r][c] != 0) {
            return memo[r][c]; // already solved
        }
        memo[r][c] = count(r + 1, c, m, n) + count(r, c + 1, m, n);
        return memo[r][c];
    }
}

Complexity

• Time: O(m · n) — each cell is solved once with O(1) work.
• Space: O(m · n) — the memo table, plus O(m + n) recursion stack.

Intuition

Flip the direction: let dp[r][c] be the number of ways to reach (r, c) from the start. The first row and first column can only be reached by going straight, so they are all 1. Every other cell is the sum of the cell above and the cell to the left.

Recurrence: dp[r][c] = dp[r - 1][c] + dp[r][c - 1], with dp[0][*] = dp[*][0] = 1.

Algorithm

1. Create dp[m][n]; set the first row and column to 1.
2. For r in 1..m-1, c in 1..n-1: dp[r][c] = dp[r-1][c] + dp[r][c-1].
3. Return dp[m-1][n-1].

Dry Run

m = 3, n = 7:

Code

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int r = 0; r < m; r++) {
            dp[r][0] = 1; // only straight down
        }
        for (int c = 0; c < n; c++) {
            dp[0][c] = 1; // only straight right
        }
        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]; // from above + from left
            }
        }
        return dp[m - 1][n - 1];
    }
}

Complexity

• Time: O(m · n) — one pass over the grid.
• Space: O(m · n) — the full table.

Intuition

Row r only needs row r - 1. Keep a single array row[c]. Before the update, row[c] still holds the value from the row above; row[c - 1] has already been updated to the current row (the cell to the left). So row[c] += row[c - 1] is exactly the recurrence.

Algorithm

1. row = [1, 1, ..., 1] of length n (the first row).
2. Repeat m - 1 times: for c from 1 to n - 1, row[c] += row[c - 1].
3. Return row[n - 1].

Dry Run

m = 3, n = 7
start      : [1, 1, 1, 1,  1,  1,  1]
after r=1  : [1, 2, 3, 4,  5,  6,  7]
after r=2  : [1, 3, 6, 10, 15, 21, 28]  → 28

Code

import java.util.Arrays;

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1); // first row: one way to each cell
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1]; // above (old row[c]) + left (new row[c-1])
            }
        }
        return row[n - 1];
    }
}

Complexity

• Time: O(m · n) — same number of updates.
• Space: O(n) — one row.

Intuition

Every path is a sequence of exactly m - 1 Down moves and n - 1 Right moves, and every such sequence is a valid path. So we just count arrangements: choose which m - 1 of the m + n - 2 steps are downs, C(m + n - 2, m - 1).

Compute it incrementally: result = result * (n - 1 + i) / i for i = 1..m-1. After step i the value equals C(n - 1 + i, i), which is always an integer, so the division is exact. Use long to avoid overflow in the intermediate product.

Algorithm

1. k = min(m, n) - 1 (choose the smaller side to minimize iterations); N = m + n - 2.
2. result = 1; for i = 1..k: result = result * (N - k + i) / i.
3. Return (int) result.

Dry Run

Code

class Solution {
    public int uniquePaths(int m, int n) {
        int total = m + n - 2;          // total moves
        int k = Math.min(m, n) - 1;     // choose positions of the shorter direction
        long result = 1;
        for (int i = 1; i <= k; i++) {
            // result becomes C(total - k + i, i); division is always exact
            result = result * (total - k + i) / i;
        }
        return (int) result;
    }
}

Complexity

• Time: O(min(m, n)) — one multiplication/division per step.
• Space: O(1).