Unique Paths in Grid - 2D Dynamic Programming — Grid Paths & Longest Common Subsequence | OneNoughtOne

0/361

Data Structures & Algorithms2D DP Problems — Grid Paths & LCS

2D Dynamic Programming — Grid Paths & Longest Common Subsequence

LevelIntermediate

Duration75 mins

Topic2D DP Problems — Grid Paths & LCS

1 / 4

Unique Paths in Grid

Extending DP to Two Dimensions

In our exploration of dynamic programming, we've tackled problems where the state could be captured by a single index—Fibonacci, climbing stairs, house robber. These 1D DP problems form the foundation. But many real-world problems require tracking two independent variables simultaneously.

Consider navigating a city grid, comparing two strings character by character, or filling a knapsack where both item indices and remaining capacity matter. These problems demand a two-dimensional state space—and with it, a 2D DP table.

The jump from 1D to 2D DP is one of the most important conceptual leaps in algorithmic thinking. Once you master it, you unlock a vast array of problems in string processing, grid navigation, sequence alignment, and optimization.

What You Will Learn

By the end of this page, you will master the classic "Unique Paths" problem and its variants. You'll understand how to formulate 2D DP problems, visualize state transitions on a grid, and implement solutions that are both correct and efficient. This problem serves as the gateway to all 2D dynamic programming.

The Unique Paths Problem

Problem Statement:

A robot is located at the top-left corner of an m × n grid. The robot can only move down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many unique paths are there to reach the destination?

Visualizing the Grid:

Imagine a 3×7 grid. The robot starts at position (0, 0) and must reach position (2, 6). At each cell, it can move right or down. The question is: in how many distinct ways can it reach the goal?

Converting Mermaid diagram...

Why This Problem Matters:

The unique paths problem is deceptively simple yet profoundly instructive. It appears in:

Grid-based games and navigation: Counting routes in mazes, board games, and pathfinding
Lattice path combinatorics: Foundation for advanced combinatorial analysis
Dynamic programming fundamentals: The canonical example for introducing 2D DP
Interview questions: Extremely common at major tech companies, often with variations

More importantly, the thinking pattern you develop here transfers directly to harder problems: grid paths with obstacles, minimum path sum, longest common subsequence, and string edit distance.

Constraints and Assumptions

We assume the grid has no obstacles (we'll add obstacles later). Movements are restricted to right and down only—no diagonal, up, or left movements. The grid dimensions m and n are positive integers, typically 1 ≤ m, n ≤ 100 for DP solutions, though combinatorial solutions handle much larger values.

The Naive Recursive Approach

Before diving into dynamic programming, let's develop intuition through recursion. This approach, while inefficient, reveals the problem's structure and exposes why DP is necessary.

Recursive Insight:

To reach cell (i, j), the robot must have come from either:

The cell directly above: (i-1, j) (if it moved down)
The cell directly to the left: (i, j-1) (if it moved right)

Therefore, the number of ways to reach (i, j) equals the sum of ways to reach (i-1, j) and (i, j-1).

Base Cases:

If we're at the starting cell (0, 0), there's exactly 1 way to be there (do nothing)
If the row index is negative (i < 0) or column index is negative (j < 0), there are 0 ways (we've gone off the grid)

unique_paths_recursive.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def unique_paths_recursive(m: int, n: int) -> int:
    """
    Count unique paths in an m x n grid using naive recursion.
    
    Time Complexity: O(2^(m+n)) - exponential, highly inefficient
    Space Complexity: O(m + n) - recursion stack depth
    """
    def count_paths(row: int, col: int) -> int:
        # Base case: Out of bounds
        if row < 0 or col < 0:
            return 0
        
        # Base case: Starting cell
        if row == 0 and col == 0:
            return 1
        
        # Recursive case: Sum paths from above and left
        paths_from_above = count_paths(row - 1, col)
        paths_from_left = count_paths(row, col - 1)
        
        return paths_from_above + paths_from_left
    
    # Start from bottom-right corner (m-1, n-1)
    return count_paths(m - 1, n - 1)
 
# Example: 3x7 grid
print(unique_paths_recursive(3, 7))  # Output: 28

The Problem: Exponential Time Complexity

This recursive solution works but is catastrophically slow. For a modest 20×20 grid, it would make over 137 billion function calls!

The issue is overlapping subproblems. Consider a 3×3 grid. To compute paths to (2, 2), we need paths to (1, 2) and (2, 1). But both of those require paths to (1, 1)—which we compute twice. As the grid grows, this redundancy explodes exponentially.

Converting Mermaid diagram...

Overlapping Subproblems Detected

Notice how (1,1) appears in both branches of the recursion tree. The cells (0,1) and (1,0) are computed four times each! This exponential blowup is the hallmark of naive recursion on problems with overlapping subproblems—exactly the scenario where dynamic programming provides dramatic improvement.

Memoization: Top-Down Dynamic Programming

The fix for overlapping subproblems is memoization: cache results of subproblems so we never recompute them. Since our state is defined by two indices (row, column), we need a 2D cache—either a 2D array or a dictionary with tuple keys.

Transformation Strategy:

Keep the recursive structure exactly as before
Before computing, check if result is already cached
After computing, store result in cache
Return cached result on subsequent calls

This simple addition transforms exponential complexity to polynomial!

unique_paths_memoization.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def unique_paths_memoization(m: int, n: int) -> int:
    """
    Count unique paths using memoization (top-down DP).
    
    Time Complexity: O(m * n) - each cell computed exactly once
    Space Complexity: O(m * n) - memo table + O(m + n) recursion stack
    """
    # Memoization cache: memo[row][col] = number of paths to (row, col)
    memo = {}
    
    def count_paths(row: int, col: int) -> int:
        # Base case: Out of bounds
        if row < 0 or col < 0:
            return 0
        
        # Base case: Starting cell
        if row == 0 and col == 0:
            return 1
        
        # Check memo before computing
        if (row, col) in memo:
            return memo[(row, col)]
        
        # Compute and store in memo
        result = count_paths(row - 1, col) + count_paths(row, col - 1)
        memo[(row, col)] = result
        
        return result
    
    return count_paths(m - 1, n - 1)
 
# Now fast even for larger grids
print(unique_paths_memoization(23, 12))  # Output: 193536720

Complexity Analysis:

Aspect	Before (Naive Recursion)	After (Memoization)
Time	O(2^(m+n))	O(m × n)
Space	O(m + n) stack	O(m × n) memo + O(m+n) stack
20×20 grid	~137 billion calls	400 calls
100×100 grid	Infeasible	10,000 calls (instant)

The improvement is astronomical. Memoization eliminates all redundant computation by ensuring each (row, col) pair is computed exactly once.

Python's functools.lru_cache

Python provides @functools.lru_cache decorator that automatically memoizes function calls. For the unique paths problem: @lru_cache(maxsize=None) on count_paths eliminates manual memo management. However, understanding manual memoization is essential—lru_cache is syntactic sugar, not magic.

Tabulation: Bottom-Up Dynamic Programming

While memoization works, it still uses recursion—and recursion has overhead. For this problem, we can eliminate recursion entirely using tabulation: build a 2D table iteratively, filling cells in an order that respects dependencies.

The DP Table:

Create an m × n table where dp[i][j] represents the number of unique paths to reach cell (i, j) from (0, 0).

Filling Order:

Since each cell depends on the cell above and the cell to the left, we fill the table from top-left to bottom-right, row by row or column by column.

Recurrence Relation:

dp[i][j] = dp[i-1][j] + dp[i][j-1]   (for i > 0 and j > 0)
dp[i][0] = 1   (only one way to reach any cell in first column: go down)
dp[0][j] = 1   (only one way to reach any cell in first row: go right)

unique_paths_tabulation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def unique_paths_tabulation(m: int, n: int) -> int:
    """
    Count unique paths using tabulation (bottom-up DP).
    
    Time Complexity: O(m * n) - visit each cell once
    Space Complexity: O(m * n) - the DP table
    """
    # Create m x n DP table initialized to 0
    dp = [[0] * n for _ in range(m)]
    
    # Base case: First row - only one way (keep going right)
    for j in range(n):
        dp[0][j] = 1
    
    # Base case: First column - only one way (keep going down)
    for i in range(m):
        dp[i][0] = 1
    
    # Fill the rest of the table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    # Answer is in bottom-right corner
    return dp[m - 1][n - 1]
 
# Example with step-by-step visualization
def unique_paths_with_table_print(m: int, n: int) -> int:
    """Show the filled DP table for understanding."""
    dp = [[0] * n for _ in range(m)]
    
    for j in range(n):
        dp[0][j] = 1
    for i in range(m):
        dp[i][0] = 1
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    # Print the table
    print("
DP Table (number of paths to each cell):")
    for row in dp:
        print(" | ".join(f"{x:3}" for x in row))
    
    return dp[m - 1][n - 1]
 
print(f"
Answer: {unique_paths_with_table_print(3, 7)}")

Visualizing the DP Table for a 3×7 Grid:

  1 |   1 |   1 |   1 |   1 |   1 |   1
  1 |   2 |   3 |   4 |   5 |   6 |   7
  1 |   3 |   6 |  10 |  15 |  21 |  28

Reading the Table:

The first row is all 1s: only one way to reach any cell by going right
The first column is all 1s: only one way to reach any cell by going down
Each interior cell is the sum of the cell above and the cell to the left
The bottom-right cell (28) is our answer

Notice the Pattern:

This is actually Pascal's Triangle rotated! The value at dp[i][j] equals C(i+j, i) = (i+j)!/(i! × j!). This combinatorial insight gives us an O(min(m,n)) mathematical solution, but the DP approach generalizes to problems where such closed-form solutions don't exist.

Why Tabulation Often Wins

No recursion overhead, no risk of stack overflow, cache-friendly memory access patterns, and easier to reason about space optimization. For grid DP problems especially, bottom-up tabulation is typically the preferred approach in production code.

Space Optimization: From O(m×n) to O(n)

Examine the recurrence closely: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Each cell only depends on:

The cell directly above it (previous row, same column)
The cell to its left (current row, previous column)

Key Insight:

We never need rows older than the previous row! This means we can reduce space from a full 2D table to just two rows (or even one row with careful implementation).

Rolling Array Technique:

Maintain only two arrays: prev_row and curr_row. After processing each row, the current row becomes the previous row for the next iteration.

unique_paths_space_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def unique_paths_two_rows(m: int, n: int) -> int:
    """
    Space-optimized version using two rows.
    
    Time Complexity: O(m * n)
    Space Complexity: O(n) - only two rows of length n
    """
    # Initialize previous row (all 1s for first row logic)
    prev_row = [1] * n
    
    for i in range(1, m):
        # Current row starts with 1 (first column always 1)
        curr_row = [1] * n
        
        for j in range(1, n):
            # dp[i][j] = dp[i-1][j] + dp[i][j-1]
            # prev_row[j] is dp[i-1][j] (cell above)
            # curr_row[j-1] is dp[i][j-1] (cell to left)
            curr_row[j] = prev_row[j] + curr_row[j - 1]
        
        # Current becomes previous for next iteration
        prev_row = curr_row
    
    return prev_row[n - 1]
 
 
def unique_paths_one_row(m: int, n: int) -> int:
    """
    Ultimate space optimization: single row, in-place updates.
    
    Time Complexity: O(m * n)
    Space Complexity: O(n) - single row (or O(min(m,n)) if we optimize further)
    """
    # Single row, all 1s initially
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            # Before update: dp[j] contains value from previous row (above)
            # dp[j-1] already updated in this iteration (left)
            dp[j] = dp[j] + dp[j - 1]
    
    return dp[n - 1]
 
 
# Verification: All three approaches give same answer
print(unique_paths_two_rows(10, 15))  # Output: 817190
print(unique_paths_one_row(10, 15))   # Output: 817190

Understanding the Single-Row Magic:

The single-row optimization works because of processing order:

We iterate left-to-right across each row
When we update dp[j], dp[j-1] has already been updated (current row's left neighbor)
But dp[j] still holds the old value (previous row's same position)
So dp[j] + dp[j-1] correctly sums "above" and "left"

This is a fundamental pattern in 2D DP space optimization. Whenever dependencies are limited to adjacent rows/columns, we can often reduce O(m×n) space to O(n) or O(m).

Space Complexity Comparison
Approach	Space Complexity	Additional Notes
Full 2D Table	O(m × n)	Easiest to understand, can trace any cell
Two Rows	O(n)	Clear separation of current/previous
Single Row	O(n)	Most compact, requires careful update order
Single Row + Swap	O(min(m, n))	Choose smaller dimension for row

Variation: Unique Paths with Obstacles

Real-world grids often have obstacles. The variation Unique Paths II adds this constraint: some cells are blocked, and the robot cannot pass through them.

Problem Modification:

Given an m × n grid where:

obstacleGrid[i][j] = 0 means the cell is empty
obstacleGrid[i][j] = 1 means the cell is blocked

Count unique paths from top-left to bottom-right, avoiding obstacles.

DP Modification:

if obstacle[i][j] == 1:
    dp[i][j] = 0  // Can't reach a blocked cell
else:
    dp[i][j] = dp[i-1][j] + dp[i][j-1]  // Normal case

The key insight: if a cell is blocked, there are zero ways to reach it, which propagates correctly through the DP.

unique_paths_with_obstacles.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    """
    Count unique paths avoiding obstacles.
    
    Args:
        obstacle_grid: 2D grid where 1 = blocked, 0 = empty
    
    Time Complexity: O(m * n)
    Space Complexity: O(n) with space optimization
    """
    m = len(obstacle_grid)
    n = len(obstacle_grid[0])
    
    # Edge case: start or end is blocked
    if obstacle_grid[0][0] == 1 or obstacle_grid[m-1][n-1] == 1:
        return 0
    
    # Space-optimized single row
    dp = [0] * n
    dp[0] = 1  # Starting cell
    
    for i in range(m):
        for j in range(n):
            # If current cell is obstacle, zero paths through it
            if obstacle_grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                # Add paths from left (dp[j] already has paths from above)
                dp[j] += dp[j - 1]
            # If j == 0 and no obstacle, dp[j] keeps its value from above
    
    return dp[n - 1]
 
 
# Example
grid = [
    [0, 0, 0],
    [0, 1, 0],  # Obstacle in the middle
    [0, 0, 0]
]
print(unique_paths_with_obstacles(grid))  # Output: 2

Understanding Obstacle Propagation:

Grid:          DP Table:
0 0 0          1 1 1
0 1 0    →     1 0 1
0 0 0          1 1 2

The obstacle at (1,1) creates a "shadow"—cells that can only be reached from one direction instead of two. The blocked cell has 0 paths, which propagates correctly.

Edge Cases to Handle:

Starting cell blocked: Return 0 immediately
Ending cell blocked: Return 0 immediately
Entire row blocked: All cells to the right become unreachable
Entire column blocked: All cells below become unreachable

The Power of Zero Propagation

Notice how elegant the solution is: we don't need special logic for "paths blocked by obstacle." Setting dp[i][j] = 0 for obstacles automatically handles all downstream effects through the normal DP recurrence. This is a hallmark of well-designed DP: the recurrence naturally handles edge cases.

Approach	Time	Space	Use When
DP (tabulation)	O(m×n)	O(n)	Obstacles, custom weights, variants
Combinatorial	O(min(m,n))	O(1)	Basic counting, large grids

2D Dynamic Programming — Grid Paths & Longest Common Subsequence

LevelIntermediate

Duration75 mins

Topic2D DP Problems — Grid Paths & LCS

1 / 4

Unique Paths in Grid

Extending DP to Two Dimensions

What You Will Learn

The Unique Paths Problem

Problem Statement:

A robot is located at the top-left corner of an m × n grid. The robot can only move down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many unique paths are there to reach the destination?

Visualizing the Grid:

Imagine a 3×7 grid. The robot starts at position (0, 0) and must reach position (2, 6). At each cell, it can move right or down. The question is: in how many distinct ways can it reach the goal?

Converting Mermaid diagram...

Why This Problem Matters:

The unique paths problem is deceptively simple yet profoundly instructive. It appears in:

Grid-based games and navigation: Counting routes in mazes, board games, and pathfinding
Lattice path combinatorics: Foundation for advanced combinatorial analysis
Dynamic programming fundamentals: The canonical example for introducing 2D DP
Interview questions: Extremely common at major tech companies, often with variations

More importantly, the thinking pattern you develop here transfers directly to harder problems: grid paths with obstacles, minimum path sum, longest common subsequence, and string edit distance.

Constraints and Assumptions

The Naive Recursive Approach

Before diving into dynamic programming, let's develop intuition through recursion. This approach, while inefficient, reveals the problem's structure and exposes why DP is necessary.

Recursive Insight:

To reach cell (i, j), the robot must have come from either:

The cell directly above: (i-1, j) (if it moved down)
The cell directly to the left: (i, j-1) (if it moved right)

Therefore, the number of ways to reach (i, j) equals the sum of ways to reach (i-1, j) and (i, j-1).

Base Cases:

If we're at the starting cell (0, 0), there's exactly 1 way to be there (do nothing)
If the row index is negative (i < 0) or column index is negative (j < 0), there are 0 ways (we've gone off the grid)

unique_paths_recursive.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def unique_paths_recursive(m: int, n: int) -> int:
    """
    Count unique paths in an m x n grid using naive recursion.
    
    Time Complexity: O(2^(m+n)) - exponential, highly inefficient
    Space Complexity: O(m + n) - recursion stack depth
    """
    def count_paths(row: int, col: int) -> int:
        # Base case: Out of bounds
        if row < 0 or col < 0:
            return 0
        
        # Base case: Starting cell
        if row == 0 and col == 0:
            return 1
        
        # Recursive case: Sum paths from above and left
        paths_from_above = count_paths(row - 1, col)
        paths_from_left = count_paths(row, col - 1)
        
        return paths_from_above + paths_from_left
    
    # Start from bottom-right corner (m-1, n-1)
    return count_paths(m - 1, n - 1)
 
# Example: 3x7 grid
print(unique_paths_recursive(3, 7))  # Output: 28

The Problem: Exponential Time Complexity

This recursive solution works but is catastrophically slow. For a modest 20×20 grid, it would make over 137 billion function calls!

Converting Mermaid diagram...

Overlapping Subproblems Detected

Memoization: Top-Down Dynamic Programming

Transformation Strategy:

Keep the recursive structure exactly as before
Before computing, check if result is already cached
After computing, store result in cache
Return cached result on subsequent calls

This simple addition transforms exponential complexity to polynomial!

unique_paths_memoization.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def unique_paths_memoization(m: int, n: int) -> int:
    """
    Count unique paths using memoization (top-down DP).
    
    Time Complexity: O(m * n) - each cell computed exactly once
    Space Complexity: O(m * n) - memo table + O(m + n) recursion stack
    """
    # Memoization cache: memo[row][col] = number of paths to (row, col)
    memo = {}
    
    def count_paths(row: int, col: int) -> int:
        # Base case: Out of bounds
        if row < 0 or col < 0:
            return 0
        
        # Base case: Starting cell
        if row == 0 and col == 0:
            return 1
        
        # Check memo before computing
        if (row, col) in memo:
            return memo[(row, col)]
        
        # Compute and store in memo
        result = count_paths(row - 1, col) + count_paths(row, col - 1)
        memo[(row, col)] = result
        
        return result
    
    return count_paths(m - 1, n - 1)
 
# Now fast even for larger grids
print(unique_paths_memoization(23, 12))  # Output: 193536720

Complexity Analysis:

Aspect	Before (Naive Recursion)	After (Memoization)
Time	O(2^(m+n))	O(m × n)
Space	O(m + n) stack	O(m × n) memo + O(m+n) stack
20×20 grid	~137 billion calls	400 calls
100×100 grid	Infeasible	10,000 calls (instant)

The improvement is astronomical. Memoization eliminates all redundant computation by ensuring each (row, col) pair is computed exactly once.

Python's functools.lru_cache

Tabulation: Bottom-Up Dynamic Programming

The DP Table:

Create an m × n table where dp[i][j] represents the number of unique paths to reach cell (i, j) from (0, 0).

Filling Order:

Since each cell depends on the cell above and the cell to the left, we fill the table from top-left to bottom-right, row by row or column by column.

Recurrence Relation:

dp[i][j] = dp[i-1][j] + dp[i][j-1]   (for i > 0 and j > 0)
dp[i][0] = 1   (only one way to reach any cell in first column: go down)
dp[0][j] = 1   (only one way to reach any cell in first row: go right)

unique_paths_tabulation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def unique_paths_tabulation(m: int, n: int) -> int:
    """
    Count unique paths using tabulation (bottom-up DP).
    
    Time Complexity: O(m * n) - visit each cell once
    Space Complexity: O(m * n) - the DP table
    """
    # Create m x n DP table initialized to 0
    dp = [[0] * n for _ in range(m)]
    
    # Base case: First row - only one way (keep going right)
    for j in range(n):
        dp[0][j] = 1
    
    # Base case: First column - only one way (keep going down)
    for i in range(m):
        dp[i][0] = 1
    
    # Fill the rest of the table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    # Answer is in bottom-right corner
    return dp[m - 1][n - 1]
 
# Example with step-by-step visualization
def unique_paths_with_table_print(m: int, n: int) -> int:
    """Show the filled DP table for understanding."""
    dp = [[0] * n for _ in range(m)]
    
    for j in range(n):
        dp[0][j] = 1
    for i in range(m):
        dp[i][0] = 1
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    # Print the table
    print("
DP Table (number of paths to each cell):")
    for row in dp:
        print(" | ".join(f"{x:3}" for x in row))
    
    return dp[m - 1][n - 1]
 
print(f"
Answer: {unique_paths_with_table_print(3, 7)}")

Visualizing the DP Table for a 3×7 Grid:

  1 |   1 |   1 |   1 |   1 |   1 |   1
  1 |   2 |   3 |   4 |   5 |   6 |   7
  1 |   3 |   6 |  10 |  15 |  21 |  28

Reading the Table:

The first row is all 1s: only one way to reach any cell by going right
The first column is all 1s: only one way to reach any cell by going down
Each interior cell is the sum of the cell above and the cell to the left
The bottom-right cell (28) is our answer

Notice the Pattern:

Why Tabulation Often Wins

Space Optimization: From O(m×n) to O(n)

Examine the recurrence closely: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Each cell only depends on:

The cell directly above it (previous row, same column)
The cell to its left (current row, previous column)

Key Insight:

We never need rows older than the previous row! This means we can reduce space from a full 2D table to just two rows (or even one row with careful implementation).

Rolling Array Technique:

Maintain only two arrays: prev_row and curr_row. After processing each row, the current row becomes the previous row for the next iteration.

unique_paths_space_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def unique_paths_two_rows(m: int, n: int) -> int:
    """
    Space-optimized version using two rows.
    
    Time Complexity: O(m * n)
    Space Complexity: O(n) - only two rows of length n
    """
    # Initialize previous row (all 1s for first row logic)
    prev_row = [1] * n
    
    for i in range(1, m):
        # Current row starts with 1 (first column always 1)
        curr_row = [1] * n
        
        for j in range(1, n):
            # dp[i][j] = dp[i-1][j] + dp[i][j-1]
            # prev_row[j] is dp[i-1][j] (cell above)
            # curr_row[j-1] is dp[i][j-1] (cell to left)
            curr_row[j] = prev_row[j] + curr_row[j - 1]
        
        # Current becomes previous for next iteration
        prev_row = curr_row
    
    return prev_row[n - 1]
 
 
def unique_paths_one_row(m: int, n: int) -> int:
    """
    Ultimate space optimization: single row, in-place updates.
    
    Time Complexity: O(m * n)
    Space Complexity: O(n) - single row (or O(min(m,n)) if we optimize further)
    """
    # Single row, all 1s initially
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            # Before update: dp[j] contains value from previous row (above)
            # dp[j-1] already updated in this iteration (left)
            dp[j] = dp[j] + dp[j - 1]
    
    return dp[n - 1]
 
 
# Verification: All three approaches give same answer
print(unique_paths_two_rows(10, 15))  # Output: 817190
print(unique_paths_one_row(10, 15))   # Output: 817190

Understanding the Single-Row Magic:

The single-row optimization works because of processing order:

We iterate left-to-right across each row
When we update dp[j], dp[j-1] has already been updated (current row's left neighbor)
But dp[j] still holds the old value (previous row's same position)
So dp[j] + dp[j-1] correctly sums "above" and "left"

This is a fundamental pattern in 2D DP space optimization. Whenever dependencies are limited to adjacent rows/columns, we can often reduce O(m×n) space to O(n) or O(m).

Space Complexity Comparison
Approach	Space Complexity	Additional Notes
Full 2D Table	O(m × n)	Easiest to understand, can trace any cell
Two Rows	O(n)	Clear separation of current/previous
Single Row	O(n)	Most compact, requires careful update order
Single Row + Swap	O(min(m, n))	Choose smaller dimension for row

Variation: Unique Paths with Obstacles

Real-world grids often have obstacles. The variation Unique Paths II adds this constraint: some cells are blocked, and the robot cannot pass through them.

Problem Modification:

Given an m × n grid where:

obstacleGrid[i][j] = 0 means the cell is empty
obstacleGrid[i][j] = 1 means the cell is blocked

Count unique paths from top-left to bottom-right, avoiding obstacles.

DP Modification:

if obstacle[i][j] == 1:
    dp[i][j] = 0  // Can't reach a blocked cell
else:
    dp[i][j] = dp[i-1][j] + dp[i][j-1]  // Normal case

The key insight: if a cell is blocked, there are zero ways to reach it, which propagates correctly through the DP.

unique_paths_with_obstacles.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    """
    Count unique paths avoiding obstacles.
    
    Args:
        obstacle_grid: 2D grid where 1 = blocked, 0 = empty
    
    Time Complexity: O(m * n)
    Space Complexity: O(n) with space optimization
    """
    m = len(obstacle_grid)
    n = len(obstacle_grid[0])
    
    # Edge case: start or end is blocked
    if obstacle_grid[0][0] == 1 or obstacle_grid[m-1][n-1] == 1:
        return 0
    
    # Space-optimized single row
    dp = [0] * n
    dp[0] = 1  # Starting cell
    
    for i in range(m):
        for j in range(n):
            # If current cell is obstacle, zero paths through it
            if obstacle_grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                # Add paths from left (dp[j] already has paths from above)
                dp[j] += dp[j - 1]
            # If j == 0 and no obstacle, dp[j] keeps its value from above
    
    return dp[n - 1]
 
 
# Example
grid = [
    [0, 0, 0],
    [0, 1, 0],  # Obstacle in the middle
    [0, 0, 0]
]
print(unique_paths_with_obstacles(grid))  # Output: 2

Understanding Obstacle Propagation:

Grid:          DP Table:
0 0 0          1 1 1
0 1 0    →     1 0 1
0 0 0          1 1 2

The obstacle at (1,1) creates a "shadow"—cells that can only be reached from one direction instead of two. The blocked cell has 0 paths, which propagates correctly.

Edge Cases to Handle:

Starting cell blocked: Return 0 immediately
Ending cell blocked: Return 0 immediately
Entire row blocked: All cells to the right become unreachable
Entire column blocked: All cells below become unreachable

The Power of Zero Propagation