LeetCode 62: Unique Paths

Problem Restatement

A robot starts at the top-left corner of an m x n grid.

The robot wants to reach the bottom-right corner.

At each step, the robot may move only:

1. Right
2. Down

We need to count how many different paths exist.

The official constraints are 1 <= m, n <= 100, and the answer is guaranteed to fit in a 32-bit integer. (leetcode.com)

Input and Output

Function shape:

def uniquePaths(m: int, n: int) -> int:
    ...

Examples

For:

m = 3
n = 7

The answer is:

28

The robot must move:

2 downs
6 rights

in some order.

Different orders produce different paths.

For:

m = 3
n = 2

The answer is:

3

The three paths are:

Right -> Down -> Down
Down -> Right -> Down
Down -> Down -> Right

First Thought: Recursive Search

A direct recursive idea is:

At each cell:

1. Move right.
2. Move down.

Then add the number of paths from both choices.

For example:

paths(row, col) =
    paths(row + 1, col) +
    paths(row, col + 1)

This works, but it recomputes the same cells many times.

For example, many different recursive paths eventually ask:

paths(2, 3)

again and again.

Key Insight

The number of paths to a cell depends only on:

1. The cell above it
2. The cell to the left of it

To reach (row, col):

• The robot must come from (row - 1, col)
• Or from (row, col - 1)

So:

dp[row][col] =
    dp[row - 1][col] +
    dp[row][col - 1]

This is dynamic programming.

Each cell stores the number of ways to reach that cell.

Base Cases

The first row has only one path.

The robot can only move right.

1 1 1 1 1

The first column also has only one path.

The robot can only move down.

1
1
1
1

So:

dp[0][col] = 1
dp[row][0] = 1

Algorithm

Create an m x n table:

dp = [[0] * n for _ in range(m)]

Fill the first row with 1.

Fill the first column with 1.

Then for every remaining cell:

dp[row][col] =
    dp[row - 1][col] +
    dp[row][col - 1]

Return:

dp[m - 1][n - 1]

Correctness

The robot may move only right or down.

Therefore every path reaching cell (row, col) must arrive either from the cell directly above (row - 1, col) or from the cell directly to the left (row, col - 1).

These two sets of paths are disjoint because the final move is different. So the total number of paths to (row, col) equals the sum of the number of paths to those two neighboring cells.

The first row has exactly one path per cell because the robot can only move right. The first column also has exactly one path per cell because the robot can only move down.

The algorithm fills the table using these facts. Since each cell is computed from already-correct neighboring cells, every value in the table becomes correct. Therefore the bottom-right cell stores the total number of unique valid paths.

Complexity

Implementation

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

        for row in range(m):
            dp[row][0] = 1

        for col in range(n):
            dp[0][col] = 1

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

        return dp[m - 1][n - 1]

Code Explanation

First create the DP table:

dp = [[0] * n for _ in range(m)]

Each cell stores the number of paths to that position.

Initialize the first column:

for row in range(m):
    dp[row][0] = 1

There is only one way to move straight down.

Initialize the first row:

for col in range(n):
    dp[0][col] = 1

There is only one way to move straight right.

Now fill the remaining cells:

for row in range(1, m):
    for col in range(1, n):

Each cell gets the sum of:

dp[row - 1][col]

and:

dp[row][col - 1]

So:

dp[row][col] = (
    dp[row - 1][col] +
    dp[row][col - 1]
)

Finally return the bottom-right corner:

return dp[m - 1][n - 1]

Space Optimization

Notice that each row depends only on:

1. The current row
2. The previous row

So we can reduce space to O(n).

The transition becomes:

dp[col] += dp[col - 1]

This updates the current row in place.

Optimized Implementation

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

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

        return dp[-1]

Testing

def run_tests():
    s = Solution()

    assert s.uniquePaths(3, 7) == 28
    assert s.uniquePaths(3, 2) == 3
    assert s.uniquePaths(1, 1) == 1
    assert s.uniquePaths(1, 5) == 1
    assert s.uniquePaths(5, 1) == 1
    assert s.uniquePaths(3, 3) == 6

    print("all tests passed")

run_tests()