Unique Paths

Intuition

Any path into cell (i, j) arrives either from the cell directly above or the cell directly to its left, so dp[i][j] = dp[i-1][j] + dp[i][j-1], with the entire first row and first column equal to 1. Computing rows top to bottom, the value we need from above is exactly the value currently stored in the same column of a single row buffer before we overwrite it. That lets us collapse the 2D table into one array of length n. Purely combinatorially the count equals C(m+n-2, m-1), since any path is a fixed arrangement of (m-1) downs among (m+n-2) total moves. The DP version avoids large factorials and overflow concerns while running in linear space. We update the row in place from left to right, accumulating contributions from the left neighbor.

Algorithm walkthrough

1. 1Create a row array of length n filled with 1s, representing the topmost row where every cell has a single path.
2. 2For each subsequent row i from 1 to m-1, process columns left to right.
3. 3For column j from 1 onward, add the left neighbor into the current cell: row[j] += row[j-1].
4. 4Before the update, row[j] still holds the value from the row above, and row[j-1] holds the freshly computed left value, so the sum matches dp[i-1][j] + dp[i][j-1].
5. 5Leave row[0] untouched since the first column always has exactly one path.
6. 6After all rows are processed, row[n-1] is the number of unique paths.

Implementation

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                row[j] += row[j - 1]
        return row[n - 1]