62. Unique Paths - Explanation

Description

There is an m x n grid where you are allowed to move either down or to the right at any point in time.

Given the two integers m and n, return the number of possible unique paths that can be taken from the top-left corner of the grid (grid[0][0]) to the bottom-right corner (grid[m - 1][n - 1]).

You may assume the output will fit in a 32-bit integer.

Example 1:

Input: m = 3, n = 6

Output: 21

Example 2:

Input: m = 3, n = 3

Output: 6

Constraints:

1 <= m, n <= 100

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, where we have two choices at each step. Can you determine the base condition and recurrence relation?

Hint 2

We recursively traverse the grid using row i and column j. At each step, we explore both possibilities: moving down or moving right, ensuring we do not go out of bounds. If we reach the bottom-right cell, we return 1.

Hint 3

This approach has exponential complexity. Can you think of a way to optimize the recursion? Maybe you should consider using a dynamic programming approach.

Hint 4

We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a 2D array can be used to store these results.

Company Tags

1. Recursion

Intuition

This is the pure recursive (brute force) way to think about the problem.

From any cell (i, j) in the grid:

You can only move right or down.
The total number of paths from (i, j) is:

paths going right + paths going down

Base ideas:

If you reach the bottom-right cell, you found one valid path.
If you go out of bounds, that path is invalid (count = 0).

So the problem naturally breaks into smaller subproblems, making recursion a direct fit.

Algorithm

Start from the top-left cell (0, 0).
At each cell (i, j):
- If (i, j) is the destination (m-1, n-1), return 1.
- If (i, j) is outside the grid, return 0.
Recursively compute:
- Paths by moving right -> (i, j + 1)
- Paths by moving down -> (i + 1, j)
Return the sum of both.
The answer is the result from (0, 0).

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        def dfs(i, j):
            if i == (m - 1) and j == (n - 1):
                return 1
            if i >= m or j >= n:
                return 0
            return dfs(i, j + 1) + dfs(i + 1, j)

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ {m + n})$
Space complexity: $O(m + n)$

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

2. Dynamic Programming (Top-Down)

Intuition

This is the optimized version of recursion using memoization.

In the brute-force approach, the same cell (i, j) is solved many times.
But the number of paths from a cell never changes, so we can store it once and reuse it.

Think of it this way:

Every cell (i, j) asks:
“How many ways can I reach the destination from here?”
Once answered, we cache it so we never recompute it.

This turns an exponential recursion into a polynomial-time solution.

Algorithm

Create a 2D memo table memo[m][n], initialized to -1.
Define a recursive function dfs(i, j):
- If (i, j) is the destination (m-1, n-1), return 1.
- If (i, j) is out of bounds, return 0.
- If memo[i][j] is already computed, return it.
Otherwise:
- Compute paths by moving right and down:
  memo[i][j] = dfs(i, j+1) + dfs(i+1, j)
Return memo[i][j].
Start recursion from (0, 0).

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = [[-1] * n for _ in range(m)]
        def dfs(i, j):
            if i == (m - 1) and j == (n - 1):
                return 1
            if i >= m or j >= n:
                return 0
            if memo[i][j] != -1:
                return memo[i][j]

            memo[i][j] =  dfs(i, j + 1) + dfs(i + 1, j)
            return memo[i][j]

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

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

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of starting from the top and recursing, we build the answer from the destination backward.

From any cell (i, j), the number of unique paths to the destination is:

paths from the cell below (i+1, j)
plus paths from the cell to the right (i, j+1)

If we already know these values, we can compute the current cell directly.

So we:

Set the destination cell to 1
Fill the grid bottom-up, right-to-left

Algorithm

Create a (m+1) x (n+1) DP table initialized with 0.
Set dp[m-1][n-1] = 1 (only one way to stay at destination).
Traverse rows from m-1 to 0 and columns from n-1 to 0.
For each cell (i, j): dp[i][j] = dp[i+1][j] + dp[i][j+1]
Return dp[0][0].

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

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] += dp[i + 1][j] + dp[i][j + 1]

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

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

4. Dynamic Programming (Space Optimized)

Intuition

Each cell only depends on:

the cell to the right (same row)
the cell below (previous row)

So instead of storing the entire 2D grid, we can keep just one row at a time.
We update the row from right to left, using values from:

the current row (newRow[j + 1])
the previous row (row[j])

This reduces space while keeping the same logic.

Algorithm

Initialize a 1D array row of size n with all 1s
(only one way to move right along the bottom row).
Repeat for m - 1 rows:
- Create a new row filled with 1s.
- Traverse columns from right to left (excluding last column).
- Update: newRow[j] = newRow[j + 1] + row[j]
- Replace row with newRow.
Return row[0] (top-left cell).

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n

        for i in range(m - 1):
            newRow = [1] * n
            for j in range(n - 2, -1, -1):
                newRow[j] = newRow[j + 1] + row[j]
            row = newRow
        return row[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

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

5. Dynamic Programming (Optimal)

Intuition

From any cell, you can reach the destination by moving:

right
down

The number of ways to reach a cell equals:

ways from the cell below + ways from the cell to the right

Instead of using a full 2D table, we notice that:

each row only depends on the row below it
so a single 1D array is enough

We keep updating this array from right to left, accumulating paths.

Algorithm

Initialize a 1D array dp of size n with all values as 1
(only one way along the last row).
For each remaining row (from bottom to top):
- Traverse columns from right to left (excluding last column).
- Update: dp[j] = dp[j] + dp[j + 1]
After all rows are processed, dp[0] contains the total number of unique paths.
Return dp[0].

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

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

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

6. Math

Intuition

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}$

Algorithm

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

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

Time & Space 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.