Space Optimisation for 2D DP
Reduce LCS and edit-distance from O(mn) to O(min(m,n)) space by keeping only the current and previous rows of the DP table.
Why Space Matters in 2D DP
A 2D DP table for strings of length 1000 requires 1000×1000 = 1,000,000 cells — roughly 8 MB for 64-bit integers. For longer sequences (DNA alignment, large text diff), this becomes impractical. The key observation is that most 2D DP recurrences only look at the current and previous row, so the entire table can be compressed into one or two 1D arrays. This is the core of 2D DP space optimisation.
# Full 2D DP: O(mn) space
# LCS for 1000-char strings
m, n = 1000, 1000
dp_2d_size = m * n * 8 # bytes (64-bit ints)
print(f'2D table: {dp_2d_size:,} bytes = {dp_2d_size//1024} KB')
# 1D rolling array: O(n) space
dp_1d_size = n * 8
print(f'1D array: {dp_1d_size:,} bytes = {dp_1d_size} bytes')
print(f'Space saving: {dp_2d_size // dp_1d_size}x')Rolling Array Pattern
The rolling array pattern replaces the full 2D table with a 1D array representing the previous row. When computing row i, you update each cell j using the current value dp[j] (which still holds the previous row's dp[i-1][j]) and the just-updated dp[j-1] (which is dp[i][j-1]). A diagonal variable captures dp[i-1][j-1] before it is overwritten. This pattern applies to LCS, edit distance, and most 2D DP problems.
# Rolling array template for 2D DP
# Before update: dp[j] holds dp[i-1][j] (previous row)
# After update: dp[j] holds dp[i][j] (current row)
def rolling_array_template(grid):
m, n = len(grid), len(grid[0])
dp = [0] * (n + 1) # represents one row
for i in range(1, m + 1):
diag = 0 # stores dp[i-1][j-1] before overwrite
for j in range(1, n + 1):
temp = dp[j] # save dp[i-1][j] before overwriting
# compute dp[i][j] using dp[j] (above) and dp[j-1] (left) and diag
dp[j] = diag + dp[j] + dp[j-1] # placeholder logic
diag = temp
return dp[n]All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP