LeetCode Problem 62

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Combinatorics

Solution

Unique Paths

Problem Understanding

The problem describes a robot moving on a rectangular m x n grid. The robot starts at the top left corner of the grid and wants to reach the bottom right corner. At every step, the robot is only allowed to move either one cell to the right or one cell downward.

The input consists of two integers:

• m, the number of rows in the grid
• n, the number of columns in the grid

The output should be a single integer representing how many distinct valid paths exist from the starting position to the destination.

To better understand the movement rules, consider a 3 x 7 grid. To go from the top left to the bottom right, the robot must move:

• Down exactly m - 1 times
• Right exactly n - 1 times

The challenge is determining how many different ways those moves can be arranged.

The constraints are important:

• 1 <= m, n <= 100

These limits are small enough for dynamic programming solutions, but large enough that brute force recursion becomes impractical. Since the result is guaranteed to fit within 2 * 10^9, standard integer types are sufficient.

Several edge cases are important:

• A 1 x 1 grid has exactly one path because the robot is already at the destination.
• A single row grid, such as 1 x 5, allows only right moves, so there is exactly one path.
• A single column grid, such as 5 x 1, allows only downward moves, so there is exactly one path.
• Large grids like 100 x 100 would make naive recursive exploration extremely slow because the number of possible paths grows exponentially.

Approaches

Brute Force Recursive Search

The most straightforward approach is to recursively explore every possible path.

At each cell, the robot has at most two choices:

• Move right
• Move down

The recursive function continues until it either:

• Reaches the bottom right corner, contributing one valid path
• Goes outside the grid boundaries, contributing zero paths

This approach is correct because it exhaustively explores every possible legal route. Every unique sequence of moves corresponds to exactly one recursive path.

However, the same subproblems are recomputed many times. For example, the number of paths from cell (2, 3) to the destination may be calculated repeatedly from different recursive branches. This duplication causes exponential growth in runtime.

For grids near the upper constraint limits, brute force recursion becomes far too slow.

Optimal Dynamic Programming

The key observation is that the number of paths to any cell depends only on the cells directly above and directly to the left.

If we define:

• dp[row][col] as the number of unique paths to reach that cell

Then:

• The robot can only arrive from above or from the left
• Therefore:

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

This recurrence naturally leads to dynamic programming.

The first row and first column each contain only one possible path because movement is restricted to a single direction there.

By filling the table row by row, every state is computed exactly once, producing an efficient solution.

We can further optimize space by using a one dimensional array because each row only depends on the previous values in the current row and the row above.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(m+n))	O(m+n)	Explores every possible path recursively
Optimal	O(m × n)	O(n)	Dynamic programming with space optimization

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Create a one dimensional DP array of size n.

Each position in the array represents the number of ways to reach a column in the current row. Using a one dimensional array reduces memory usage while preserving correctness. 2. Initialize every value in the array to 1.

The first row has only one possible path to every cell because the robot can only move right.

Example for n = 5:

[1, 1, 1, 1, 1]

3. Iterate through the remaining rows starting from row 1.

For every additional row, update the number of paths for each column. 4. For each column starting from column 1, update:

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

Here:

• dp[col] represents the number of paths from above
• dp[col - 1] represents the number of paths from the left

Adding them gives the total number of paths to the current cell.

1. Continue updating the array until all rows are processed.
2. Return the final value in the array.

The last element represents the number of unique paths to the bottom right corner.

Why it works

The algorithm works because every valid path to a cell must come from either the cell directly above or directly to the left. The dynamic programming recurrence captures this property exactly. Since the algorithm processes cells in an order where dependencies are already computed, every state receives the correct total number of paths.

Python Solution

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]

The solution begins by creating a one dimensional array named dp. Every value starts as 1 because there is exactly one way to reach any cell in the first row.

The outer loop iterates through each additional row. The first row does not require computation because its values are already initialized correctly.

The inner loop processes columns from left to right. For every cell, the current value represents paths coming from above, while the previous value in the array represents paths coming from the left.

By updating:

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

the algorithm combines both possible incoming directions.

After all rows are processed, the last element contains the total number of unique paths to the destination.

Go Solution

func uniquePaths(m int, n int) int {
    dp := make([]int, n)

    for i := 0; i < n; i++ {
        dp[i] = 1
    }

    for row := 1; row < m; row++ {
        for col := 1; col < n; col++ {
            dp[col] += dp[col-1]
        }
    }

    return dp[n-1]
}

The Go implementation follows the same dynamic programming logic as the Python version.

A slice is used instead of a Python list. Go requires explicit initialization of the slice values to 1.

The constraints guarantee that the final answer fits within a 32 bit signed integer, so the standard int type is sufficient for LeetCode.

Worked Examples

Example 1

Input: m = 3, n = 7

Initial DP array:

Step	DP State
Initial	[1, 1, 1, 1, 1, 1, 1]

Process row 1:

Column	Calculation	DP State
1	1 + 1 = 2	[1, 2, 1, 1, 1, 1, 1]
2	1 + 2 = 3	[1, 2, 3, 1, 1, 1, 1]
3	1 + 3 = 4	[1, 2, 3, 4, 1, 1, 1]
4	1 + 4 = 5	[1, 2, 3, 4, 5, 1, 1]
5	1 + 5 = 6	[1, 2, 3, 4, 5, 6, 1]
6	1 + 6 = 7	[1, 2, 3, 4, 5, 6, 7]

Process row 2:

Column	Calculation	DP State
1	2 + 1 = 3	[1, 3, 3, 4, 5, 6, 7]
2	3 + 3 = 6	[1, 3, 6, 4, 5, 6, 7]
3	4 + 6 = 10	[1, 3, 6, 10, 5, 6, 7]
4	5 + 10 = 15	[1, 3, 6, 10, 15, 6, 7]
5	6 + 15 = 21	[1, 3, 6, 10, 15, 21, 7]
6	7 + 21 = 28	[1, 3, 6, 10, 15, 21, 28]

Final answer:

28

Example 2

Input: m = 3, n = 2

Initial state:

Step	DP State
Initial	[1, 1]

Process row 1:

Column	Calculation	DP State
1	1 + 1 = 2	[1, 2]

Process row 2:

Column	Calculation	DP State
1	2 + 1 = 3	[1, 3]

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every grid cell is processed exactly once
Space	O(n)	Only one row of DP values is stored

The nested loops iterate through all cells in the grid exactly once, producing linear work relative to the number of cells. The space optimization works because each state depends only on the current row and the previous value in the same row.

Test Cases

solution = Solution()

assert solution.uniquePaths(3, 7) == 28  # standard example
assert solution.uniquePaths(3, 2) == 3   # small rectangular grid
assert solution.uniquePaths(1, 1) == 1   # single cell grid
assert solution.uniquePaths(1, 5) == 1   # single row
assert solution.uniquePaths(5, 1) == 1   # single column
assert solution.uniquePaths(2, 2) == 2   # smallest non-trivial square
assert solution.uniquePaths(3, 3) == 6   # small square grid
assert solution.uniquePaths(7, 3) == 28  # symmetry check
assert solution.uniquePaths(10, 10) == 48620  # medium sized grid
assert solution.uniquePaths(23, 12) == 193536720  # large valid result

Test	Why
m=3, n=7	Verifies standard example
m=3, n=2	Confirms multiple path combinations
m=1, n=1	Tests minimal grid
m=1, n=5	Tests single row edge case
m=5, n=1	Tests single column edge case
m=2, n=2	Smallest grid with branching
m=3, n=3	Validates square grid behavior
m=7, n=3	Confirms symmetry of the solution
m=10, n=10	Medium sized stress test
m=23, n=12	Large input within constraints

Edge Cases

Single Cell Grid

A 1 x 1 grid is a special case because the robot already starts at the destination. A buggy implementation might incorrectly return 0 if it assumes movement is required. This implementation correctly returns 1 because the DP array starts initialized with ones and no loops execute.

Single Row or Single Column

If either m == 1 or n == 1, the robot has only one possible route. Some implementations accidentally attempt invalid transitions or create incorrect DP dimensions. Here, the loops naturally handle these cases because either the outer loop or inner loop never executes, leaving the result as 1.

Large Grid Sizes

Large inputs like 100 x 100 expose inefficiencies in recursive solutions because the number of possible paths grows extremely quickly. A brute force implementation would time out due to exponential recursion. The dynamic programming approach avoids recomputation entirely and processes each state once, ensuring efficient execution even at the maximum constraints.