Unique Paths · DSA Prep

The number of ways to reach any cell is the number of ways to reach the cell above it, plus the number of ways to reach the cell to its left — those are the only two moves that could have landed you there.

Brute Force Recursion

Time O(2^(m+n))Space O(m+n)

Recurse from the start: at each cell, branch into “move down” and “move right”, and count the paths that reach the bottom-right corner.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def paths(r: int, c: int) -> int:
            if r == m - 1 or c == n - 1:
                return 1
            return paths(r + 1, c) + paths(r, c + 1)
        return paths(0, 0)

Correct, but the same (r, c) is reached by many different paths and gets recomputed from scratch every time — exponential blow-up.

2-D DP Table (Bottom-Up)

OptimalTime O(m·n)Space O(m·n)

Cache the answer for every cell instead of recomputing it. The entire top row and left column are base cases (only one possible path: straight right, or straight down), and every other cell combines the cell above and the cell to the left.

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

Filling the table for a 3 x 3 grid:

1 / 5

comparingseenresult

Base case: the top row and left column each have exactly one path (a straight line of moves).

Complexity: each of the m·n cells is computed once with O(1) work → O(m·n) time, O(m·n) space for the table.

1-D Rolling Array

Time O(m·n)Space O(n)

Each row of the table only ever depends on the row directly above it. Instead of storing the whole grid, keep a single row and update it in place, left to right — row[c] += row[c-1] reuses the “row above” value that’s still sitting in row[c] before it gets overwritten.

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

Same O(m·n) time, but space drops from the full grid to a single row — O(n) space.