Space Optimization - Learning Module

Loading content...

0/276

Reducing 2D DP to 1D

The Memory Efficiency Imperative

You've mastered the art of designing DP solutions—defining states, identifying recurrence relations, and building tables that solve complex optimization problems. But there's a lurking challenge that becomes critical as your problems scale: memory consumption.

Consider the classic 0/1 Knapsack problem with n = 10,000 items and capacity W = 100,000. A straightforward 2D DP solution requires a table of size n × W = 10,000 × 100,000 = 1 billion cells. At 4 bytes per integer, that's 4 GB of memory—for a single algorithm!

This isn't just a theoretical concern. In competitive programming, memory limits are typically 256 MB or 512 MB. In production systems, excessive memory usage causes cache misses, swap thrashing, and out-of-memory crashes. Space optimization isn't a luxury—it's often a necessity.

What You Will Learn

By the end of this page, you will understand the fundamental technique of reducing 2D DP tables to 1D arrays. You'll learn to analyze dependency patterns that enable this optimization, implement the transformation systematically, and recognize the dramatic space savings this technique enables—often reducing O(n²) or O(n × m) space to O(n) or O(m).

The Foundation — Understanding DP Table Dependencies

Before we can optimize space, we must deeply understand how cells in a DP table depend on each other. This dependency structure is the key that unlocks space optimization.

In bottom-up DP, we fill a table cell by cell. Each cell dp[i][j] depends on previously computed cells. The pattern of these dependencies determines whether we can reduce dimensions.

The Critical Insight: If every cell in row i depends only on cells in row i-1 (the immediately previous row), then we don't need to store all rows—we only need the current row and the previous row. And with careful implementation, we can often reduce this further to a single row!

Common Dependency Patterns in 2D DP

•Single-row dependency: dp[i][j] depends only on cells in row i-1. Examples: Knapsack, Coin Change, Edit Distance.
•Same-row + previous-row: dp[i][j] depends on dp[i-1][...] and dp[i][j-1] (cells in the same row to the left). Examples: Unique Paths, minimum path sum.
•Multi-row dependency: dp[i][j] depends on rows i-1, i-2, or earlier. These typically cannot be reduced to 1D directly.
•Diagonal dependency: dp[i][j] depends on dp[i-1][j-1] (previous row, previous column). Requires careful handling.

The Golden Rule of Space Optimization

If each row only depends on the immediately previous row, the 2D table can be reduced to two 1D arrays (current and previous). If we're even more careful with our iteration order, we can often reduce it to a single 1D array.

Visualizing the Transformation

Let's visualize what happens when we reduce a 2D DP table to 1D. Consider the 0/1 Knapsack problem with the following recurrence:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

Notice that dp[i][w] depends only on values from row i-1. The current row's values are computed entirely from the previous row.

2D Knapsack Table — Row Dependencies
Capacity →	2	3	4	5
Item 0 (base)	0	0	0	0
Item 1 (w=2,v=3)	3←	3	3	3
Item 2 (w=3,v=4)	3	4←	4	7←
Item 3 (w=4,v=5)	3	4	5←	7

The arrows (←) indicate dependencies from the previous row. Cell dp[2][5] = 7 comes from max(dp[1][5]=3, dp[1][2]+4=7).

Since row i only needs row i-1, after computing row i, row i-2 becomes useless. We're wasting memory storing all those old rows!

The insight: Instead of storing all n rows, we could:

Use two arrays: prev[] and curr[], alternating between them
Or better: use a single array and update it in-place (with the right iteration order)

Why Iteration Order Matters

When reducing to a single 1D array, we must process elements in an order that doesn't overwrite values we still need. For Knapsack, this means iterating from right to left (decreasing capacity) so we don't accidentally use 'new' values when we need 'old' values.

The Technique — Step by Step

Let's formalize the process of reducing a 2D DP solution to 1D. This is a systematic technique you can apply to many problems.

The 2D → 1D Reduction Process

•Analyze dependencies: For each cell dp[i][j], identify exactly which cells it depends on. List them: dp[i-1][j]? dp[i-1][j-1]? dp[i][j-1]?
•Verify single-row dependency: Confirm that all dependencies come from the immediately previous row (possibly plus same-row cells to the left).
•Identify the dimension to eliminate: The 'outer' dimension (typically the item/character index) can be eliminated if dependencies follow the pattern.
•Determine iteration order: This is critical! If we need dp[i-1][j] (same column, previous row), we must not overwrite dp[j] before using it. Often this means reverse iteration.
•Transform the code: Replace dp[i][j] with dp[j]. Remove the outer array dimension. Adjust initialization.
•Handle special cases: Base cases, boundary conditions, and diagonal dependencies may need special attention.

Example: 0/1 Knapsack Transformation

Let's see this in action with the 0/1 Knapsack problem.

knapsack_2d_vs_1d.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
# 2D Solution — O(n × W) space
def knapsack_2d(weights, values, W):
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            # Don't take item i
            dp[i][w] = dp[i-1][w]
            # Take item i (if possible)
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w], 
                               dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][W]  # Space: O(n × W)
 
# 1D Solution — O(W) space
def knapsack_1d(weights, values, W):
    n = len(weights)
    # dp[w] = max value with capacity w (using items processed so far)
    dp = [0] * (W + 1)
    
    for i in range(n):
        # CRITICAL: Iterate RIGHT to LEFT!
        # This ensures we use dp[w - weights[i]] from the PREVIOUS iteration
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]  # Space: O(W)
 
# Why right-to-left?
# If we go left-to-right: dp[w - weight] might already be updated
# for the current item, essentially allowing multiple copies of the item!
# Right-to-left ensures we use values from the "previous row" conceptually.

Why Iteration Order is Critical

The choice of iteration order in 1D DP is not arbitrary—it's the linchpin of correctness. Let's understand this deeply.

Consider what happens in Knapsack when we iterate left-to-right (the wrong way):

Left-to-Right Iteration (WRONG for 0/1 Knapsack)
Step	Processing	dp[5]	Problem
Before	Item: weight=2, value=3	0	—
w=2	dp[2] = max(0, dp[0]+3) = 3	0	dp[2] now = 3
w=4	dp[4] = max(0, dp[2]+3) = 6	0	Uses NEW dp[2]=3!
w=5	dp[5] = max(0, dp[3]+3) = 3	3	Incorrect!

The problem: When we computed dp[4], we used dp[2] which had already been updated for the current item. We're essentially counting the same item twice—taking it at capacity 2 and again at capacity 4. This converts 0/1 Knapsack into Unbounded Knapsack!

The Iteration Order Rules

For 0/1 Knapsack (each item used at most once): Iterate RIGHT-TO-LEFT. This ensures that when we access dp[w - weight], it still contains the value from before processing the current item.

For Unbounded Knapsack (unlimited copies): Iterate LEFT-TO-RIGHT. We want to reuse updated values, allowing multiple copies of items.

Right-to-Left Iteration (CORRECT for 0/1 Knapsack)
Step	Processing	dp values used	Result
Before	Item: weight=2, value=3	dp = [0,0,0,0,0,0]	—
w=5	dp[5] = max(0, dp[3]+3) = 3	dp[3]=0 (old)	✓ Correct
w=4	dp[4] = max(0, dp[2]+3) = 3	dp[2]=0 (old)	✓ Correct
w=3	dp[3] = max(0, dp[1]+3) = 3	dp[1]=0 (old)	✓ Correct
w=2	dp[2] = max(0, dp[0]+3) = 3	dp[0]=0 (old)	✓ Correct

By iterating right-to-left, we always access dp[w - weight] before we've overwritten it with the current item's computation. This preserves the semantic of the 2D recurrence where row i depends on row i-1.

A General Framework for Iteration Order

Let's establish a general framework for determining the correct iteration order when reducing 2D DP to 1D.

Iteration Order Decision Framework

•If dp[i][j] depends on dp[i-1][j'] where j' < j: We need values from smaller indices in the previous row. Iterate RIGHT-TO-LEFT (decreasing j) to preserve these values.
•If dp[i][j] depends on dp[i-1][j'] where j' > j: We need values from larger indices in the previous row. Iterate LEFT-TO-RIGHT (increasing j) to preserve these values.
•If dp[i][j] depends on dp[i][j'] where j' < j (same row, left): We need values already updated in the current row. Iterate LEFT-TO-RIGHT.
•If dp[i][j] depends on dp[i-1][j] (same column, previous row): The value at index j from the previous iteration. This is automatically the current dp[j] before update, so either direction works for this dependency alone.

Combining Dependencies:

Real problems often have multiple dependencies. Analyze each one:

Recurrence	Dependencies	Iteration Order
`dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val)`	prev[w], prev[w-wt] (smaller)	Right-to-left
`dp[i][w] = dp[i-1][w] + dp[i][w-1]`	prev[w], curr[w-1]	Left-to-right
`dp[i][j] = dp[i-1][j] + dp[i-1][j-1]`	prev[j], prev[j-1]	Right-to-left

When dependencies conflict (some want left-to-right, others right-to-left), you typically need two arrays (current and previous) rather than a single array.

The Mental Model

Think of the 1D array as a 'sliding window' over the 2D table. Before each iteration of the outer loop, the array contains values from the previous row. After the inner loop completes, it contains values from the current row. The iteration order determines which 'version' of each cell you see during computation.

Practical Example — Edit Distance

Edit Distance (Levenshtein Distance) is a classic 2D DP problem that demonstrates a more nuanced space optimization. The recurrence is:

dp[i][j] = dp[i-1][j-1]                if s1[i-1] == s2[j-1]
dp[i][j] = 1 + min(dp[i-1][j],         // delete from s1
                   dp[i][j-1],          // insert into s1
                   dp[i-1][j-1])        // replace in s1

Dependency analysis:

dp[i-1][j-1] — diagonal (previous row, previous column)
dp[i-1][j] — directly above (previous row, same column)
dp[i][j-1] — directly left (same row, previous column)

This is tricky! We depend on both the previous row AND the current row (for dp[i][j-1]).

edit_distance_optimization.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
# Space-optimized Edit Distance — O(min(m, n)) space
def edit_distance_optimized(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    
    # Ensure s2 is the shorter string (we use O(len(s2)) space)
    if m < n:
        s1, s2, m, n = s2, s1, n, m
    
    # Current row of the DP table
    dp = list(range(n + 1))  # Base case: dp[0..n] = 0..n
    
    for i in range(1, m + 1):
        # 'diagonal' holds dp[i-1][j-1] as we iterate
        diagonal = dp[0]
        dp[0] = i  # Base case: editing first i chars of s1 to empty string
        
        for j in range(1, n + 1):
            # Save the current dp[j] before overwriting (it becomes next diagonal)
            temp = dp[j]
            
            if s1[i-1] == s2[j-1]:
                dp[j] = diagonal  # No operation needed
            else:
                dp[j] = 1 + min(
                    dp[j],      # dp[i-1][j] — delete (above, not yet updated)
                    dp[j-1],    # dp[i][j-1] — insert (left, already updated)
                    diagonal    # dp[i-1][j-1] — replace
                )
            
            diagonal = temp  # Move diagonal for next iteration
    
    return dp[n]
 
# Key insight: We iterate LEFT-TO-RIGHT because we need dp[j-1] from
# the current row. But we also need dp[i-1][j-1] (diagonal) from the
# previous row. We save it in a variable before overwriting!

Notice the diagonal trick: We save dp[j] in a temporary variable before updating it. This preserved value serves as dp[i-1][j-1] for the next column's computation. This elegant technique handles the diagonal dependency without needing a full second array.

Additional Optimization

We also swap strings to ensure we use the shorter string's length for the DP array. This gives O(min(m, n)) space instead of O(n). For strings of length 1000 and 10, we use 11 cells instead of 1001!

Another Example — Longest Common Subsequence

The Longest Common Subsequence (LCS) problem has a similar dependency structure to Edit Distance:

dp[i][j] = dp[i-1][j-1] + 1           if s1[i-1] == s2[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise

Dependencies: diagonal dp[i-1][j-1], above dp[i-1][j], left dp[i][j-1].

We apply the same diagonal-saving technique:

lcs_space_optimized.py
Python
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
def lcs_optimized(s1: str, s2: str) -> int:
    """
    Space-optimized LCS: O(min(m, n)) space
    """
    m, n = len(s1), len(s2)
    
    # Use shorter string for the 1D array
    if m < n:
        s1, s2, m, n = s2, s1, n, m
    
    dp = [0] * (n + 1)
    
    for i in range(1, m + 1):
        diagonal = 0  # dp[i-1][0] = 0 always
        
        for j in range(1, n + 1):
            temp = dp[j]  # Save dp[i-1][j] before overwriting
            
            if s1[i-1] == s2[j-1]:
                dp[j] = diagonal + 1  # Character matches
            else:
                dp[j] = max(dp[j], dp[j-1])  # Max of above and left
            
            diagonal = temp  # dp[i-1][j] becomes dp[i-1][j-1] for next column
    
    return dp[n]
 
# Comparison:
# 2D version: O(m × n) space
# 1D version: O(min(m, n)) space
# 
# For LCS of two 10,000-character strings:
# 2D: 100,000,000 cells × 4 bytes = 400 MB
# 1D: 10,000 cells × 4 bytes = 40 KB (10,000x reduction!)

The Pattern Emerges

Many 2D DP problems with dependencies on (i-1, j-1), (i-1, j), and (i, j-1) can be optimized using the same technique: iterate left-to-right, save the diagonal in a variable, and swap strings to minimize array size.

Summary: Reducing 2D DP to 1D

Let's consolidate the key insights from this page:

Key Takeaways

•Space optimization is often necessary — 2D DP tables can consume prohibitive memory for large inputs.
•Analyze dependencies first — The key to reduction is identifying that each row depends only on the previous row.
•Iteration order determines correctness — Right-to-left for 0/1-type problems (using previous values), left-to-right when using current-row values.
•The diagonal trick — When depending on (i-1, j-1), save the value in a variable before overwriting.
•Swap to minimize — Use the smaller dimension for the 1D array to achieve O(min(m, n)) space.
•Correctness over optimization — Always verify your optimized solution against example cases. It's easy to get iteration order wrong!

Space Savings Summary
Problem	2D Space	1D Space	Reduction
0/1 Knapsack	O(n × W)	O(W)	n-fold
Coin Change	O(n × amount)	O(amount)	n-fold
Edit Distance	O(m × n)	O(min(m, n))	max(m,n)-fold
LCS	O(m × n)	O(min(m, n))	max(m,n)-fold
Unique Paths	O(m × n)	O(min(m, n))	max(m,n)-fold

What's next:

In the next page, we'll explore the Rolling Array Technique — a generalization of this approach that handles cases where you need more than just the previous row, and provides a cleaner mental model for multi-row dependencies.

Page Complete

You now understand the fundamental technique of reducing 2D DP tables to 1D arrays. This skill will dramatically reduce memory usage in your DP solutions and is essential for handling large-scale optimization problems.