Unique Paths (LeetCode 62)

The problem

A robot starts at the top-left corner of an m × n grid and wants to reach the bottom-right corner. It can only move right or down. Return how many different paths it can take.

Input:  m = 3, n = 7
Output: 28

Every path makes exactly 2 down moves and 6 right moves in some order, and there are 28 such orders.

How to think about it

Start with brute force. Recursively try going right and going down from every cell. Each path has m + n - 2 moves and each step branches twice, so this is exponential. The same cells are reached by many different routes and recounted each time.

The key insight: look at the last move into a cell. You can only enter cell (i, j) from the cell above it or the cell to its left. So dp[i][j] = dp[i-1][j] + dp[i][j-1]. The whole first row and first column are 1, since there is only one way to travel along an edge.

One row is enough. Row i needs only row i-1. Keep a single array dp of length n. Before you update dp[j], it still holds the value from the row above; dp[j-1] has already been updated to this row’s left neighbour. So dp[j] += dp[j-1] is exactly “above + left”.

Which pattern is this? 2-D grid DP. The tell is “count paths in a grid moving only right/down”: each cell depends on two neighbours you’ve already computed. (There’s also a closed form, C(m+n-2, m-1), but interviewers usually want the DP.)

Approach

1. Make dp = [1] * n for the first row.
2. For each remaining row (m - 1 times), for j from 1 to n - 1: dp[j] += dp[j-1]. dp[0] stays 1 (the first column).
3. Return dp[-1].

Solution

def unique_paths(m, n):
    dp = [1] * n                                  # first row: one way to each cell
    for _ in range(1, m):
        for j in range(1, n): dp[j] += dp[j-1]    # above (old dp[j]) + left (new dp[j-1])
    return dp[-1]
# unique_paths(3, 7) -> 28

Dry run

For m = 3, n = 7, the dp row after each pass:

The last cell of the last row is 28.

Complexity

• Time: O(m · n). Every cell is computed once.
• Space: O(n). One row instead of the full m × n table.

Edge cases and pitfalls

• A single row or column (m = 1 or n = 1) returns 1: the loops do nothing and dp[-1] is 1.
• Order inside the row matters. j must go left to right so dp[j-1] is already this row’s value.
• Swap to keep memory small. If m is much smaller than n, iterate the other way and keep a row of length m.
• The closed form C(m+n-2, m-1) is O(min(m, n)), worth mentioning as a follow-up.

Related problems

• Unique Paths II (LeetCode 63): the same grid with blocked cells.
• Minimum Path Sum (LeetCode 64): same moves, but minimise a cost instead of counting.
• Climbing Stairs (LeetCode 70): the 1-D version of “sum the ways from your predecessors”.