Unique Paths

How it works

To go from the top-left to the bottom-right of an m x n grid, you can only move right or down.

• You must move down (m - 1) times
• You must move right (n - 1) times

So overall, you make (m + n - 2) moves.

The problem becomes:

In how many different ways can we arrange these right and down moves?

This is a combinations problem:

• Choose positions for the right moves (or down moves)

That gives: binom{m+n-2}{n-1}

Steps

1. If either m or n is 1, return 1 (only one path).
2. Always use the smaller value between m and n to reduce calculations.
3. Compute the combination value iteratively (without factorials).
4. Return the final result.

Complexity

• Time complexity: O(min(m, n))
• Space complexity: O(1)

Where m is the number of rows and n is the number of columns.

Things to watch for

Confusing Rows and Columns with Moves

Misunderstanding that an m x n grid requires m - 1 down moves and n - 1 right moves (not m and n). The total moves is (m - 1) + (n - 1) = m + n - 2.

Wrong Base Case in Recursion

Returning 1 when reaching any boundary instead of only the destination cell. The base case should trigger only at (m-1, n-1), not when hitting the last row or column.

Integer Overflow in Math Solution

When computing combinations for larger grids, intermediate multiplication can overflow. Use long types and divide as you multiply to keep values manageable.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        if m < n:
            m, n = n, m

        res = j = 1
        for i in range(m, m + n - 1):
            res *= i
            res //= j
            j += 1

        return res

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        if (m < n) {
            swap(m, n);
        }

        long long res = 1;
        int j = 1;
        for (int i = m; i < m + n - 1; i++) {
            res *= i;
            res /= j;
            j++;
        }

        return res;
    }
};