Space Optimization Techniques

Learn the core strategies used to collapse DP memory footprints from quadratic to linear or even constant space.

Common Tactics

The "Trade-Off" Rule

"In most cases, space optimization makes the code harder to read but significantly reduces memory pressure. Always favor clarity in interviews unless the constraints explicitly demand optimized memory."

Rolling Arrays

O(N^2) → O(N)

The most common technique for 2D DP. If dp[i][j] only depends on dp[i-1], we only need two rows: current and previous.

Typical Examples

FibonacciLCSEdit Distance

Key Mechanism

By identifying that dp[i][j] depends only on dp[i-1], we can reuse the same rows repeatedly using a modulo operator (i % 2) or simply swapping pointers.

Implementation Pattern

Pseudocode

Python

1# Instead of dp[N][M]
2dp = array[2][M]
3for i in 1..N:
4    for j in 1..M:
5        current = i % 2
6        prev = (i - 1) % 2
7        dp[current][j] = dp[prev][j-1] + ...