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.
Space Optimisation for 2D DP is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]LCS with O(min m,n) Space
For LCS, ensure text1 is the shorter string (so n is small). Allocate a 1D array of size n+1. Process row by row. At each cell: save temp = dp[j] (this is dp[i-1][j]). Then: if characters match, dp[j] = diag + 1; else dp[j] = max(dp[j], dp[j-1]). Finally set diag = temp. After all rows, dp[n] holds the LCS length.
def lcs_space_opt(text1, text2):
# Ensure text2 is the shorter one
if len(text1) < len(text2):
text1, text2 = text2, text1
m, n = len(text1), len(text2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
diag = 0
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j]
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_space_opt('ABCBDAB', 'BDCABA')) # 4
print(lcs_space_opt('AGGTAB', 'GXTXAYB')) # 4Edit Distance with O(n) Space
Edit distance uses the same rolling pattern. The initial 1D array represents row 0: dp[j] = j (inserting j characters). For each row i, set dp[0] = i (deleting i characters) and save diag = dp[0] before the update. In the inner loop, save temp = dp[j], compute the new value from insert (dp[j-1]+1), delete (dp[j]+1), and replace (diag + cost), then set diag = temp.
def edit_dist_opt(s, t):
m, n = len(s), len(t)
dp = list(range(n + 1)) # row 0: dp[0][j] = j
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0] before dp[0] update
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j]
cost = 0 if s[i-1] == t[j-1] else 1
dp[j] = min(
dp[j-1] + 1, # insert
dp[j] + 1, # delete
diag + cost # replace or match
)
diag = temp
return dp[n]
print(edit_dist_opt('horse', 'ros')) # 3
print(edit_dist_opt('intention', 'execution')) # 5Min Path Sum with O(n) Space
For Min Path Sum on a grid, the 1D rolling array starts as the first row prefix sums (only one way into each cell on the first row). For each subsequent row, update left-to-right: dp[j] before update is the value from the row above (dp[i-1][j]), and dp[j-1] just updated is from the left. No diagonal is needed here because min path sum doesn't require the diagonal cell.
def min_path_sum_opt(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
# Update first column (only from above)
dp[0] += grid[i][0]
for j in range(1, n):
# min of above (dp[j] = old) and left (dp[j-1] = updated)
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_opt(grid)) # 7When Diagonal Access is Needed
Not all 2D DP problems can be compressed with a simple rolling array because some need the diagonal element dp[i-1][j-1] after dp[j] has been overwritten. The fix is always the same: save temp = dp[j] before updating it, use it as diag for the next column's computation. This one-cell lookahead handles all three-direction recurrences (LCS, edit distance) cleanly.
# Recap: the diagonal save pattern
# Without it: dp[j-1] updated (left) and dp[j] about to be overwritten
# With it:
def show_diagonal_pattern(s1, s2):
n = len(s2)
dp = [0] * (n + 1)
for ch1 in s1:
diag = 0 # was dp[i-1][0] = 0 for LCS
for j, ch2 in enumerate(s2, 1):
temp = dp[j] # SAVE before overwrite
if ch1 == ch2:
dp[j] = diag + 1 # use saved diagonal
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp # advance diagonal
return dp[n]
print(show_diagonal_pattern('ABCBDAB', 'BDCABA')) # 42D Knapsack Space Optimisation
The 0/1 Knapsack problem also benefits from space optimisation. The full 2D table has dimensions (n_items+1) × (capacity+1). The rolling array reduces it to O(capacity). The critical difference from LCS/edit-distance: iterate the capacity dimension in reverse (from high to low). This ensures each item is counted at most once — iterating forward would allow an item to be selected multiple times.
def knapsack_01(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Reverse order: prevents using the same item twice
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
cap = 7
print(knapsack_01(weights, values, cap)) # 9 (items 3+4: weight 3+4=7, value 4+5=9)Forward vs Reverse Iteration
Knowing which direction to iterate the inner loop is critical: reverse for 0/1 knapsack (each item used at most once — looking back at previous states prevents re-use). Forward for unbounded knapsack (each item can be reused — looking at already-updated states allows multiple uses). Getting this wrong silently changes 0/1 to unbounded or vice versa. Always confirm the constraint before choosing direction.
# 0/1 Knapsack: each item used AT MOST ONCE → iterate reverse
def knapsack_01_demo(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w-1, -1): # REVERSE
dp[c] = max(dp[c], dp[c-w] + v)
return dp[cap]
# Unbounded Knapsack: items can be reused → iterate forward
def knapsack_unbounded(weights, values, cap):
dp = [0] * (cap + 1)
for c in range(1, cap + 1):
for w, v in zip(weights, values):
if c >= w:
dp[c] = max(dp[c], dp[c-w] + v) # FORWARD
return dp[cap]
print(knapsack_01_demo([2,3],[3,4],5)) # 7
print(knapsack_unbounded([2,3],[3,4],5)) # 8 (use weight-2 twice: 3+3=6? or 4+... )Unique Paths with O(n) Space
For unique paths, the entire table can be replaced by a single row. Initialise all cells to 1 (the first row). For each subsequent row, update left-to-right: dp[j] += dp[j-1]. No diagonal is needed because the recurrence only uses the cell above (dp[j], current value before update) and the cell to the left (dp[j-1], already updated). This is the simplest 2D→1D compression.
def unique_paths_opt(m, n):
dp = [1] * n # first row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # above (dp[j]) + left (dp[j-1])
return dp[n-1]
# With obstacles
def unique_paths_obstacles_opt(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = 1
for i in range(m):
if grid[i][0] == 1: dp[0] = 0 # blocked column
for j in range(1, n):
if grid[i][j] == 1: dp[j] = 0 # blocked
else: dp[j] += dp[j-1]
return dp[n-1]
print(unique_paths_opt(3, 7)) # 28
print(unique_paths_obstacles_opt([[0,0,0],[0,1,0],[0,0,0]])) # 2Two-Row Buffer for Complex Recurrences
When the recurrence needs cells from two or more previous rows (e.g., some interval DP variants or 3D DP reductions), a two-row buffer is used: maintain prev and curr arrays, swap them after each row. This gives O(2n) = O(n) space. For recurrences looking back k rows, maintain k arrays as a circular buffer. This generalises the one-row rolling array pattern.
def lcs_two_row_buffer(s1, s2):
m, n = len(s1), len(s2)
prev = [0] * (n + 1) # dp[i-1]
curr = [0] * (n + 1) # dp[i]
for i in range(1, m + 1):
curr[0] = 0
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, prev # swap (curr becomes prev)
return prev[n] # after swap, prev holds the last computed row
print(lcs_two_row_buffer('ABCBDAB', 'BDCABA')) # 4When Space Optimisation is Not Possible
Space optimisation is not always possible. If you need to reconstruct the optimal solution (not just its value), you generally need the full table for backtracking. Workarounds include: (1) Storing a separate decision table of the same size. (2) Using Hirschberg's algorithm, which computes LCS in O(mn) time and O(min(m,n)) space including reconstruction by dividing the problem at the midpoint recursively. (3) Accepting O(mn) space when reconstruction is required.
# When reconstruction needed: must keep full table or use Hirschberg
# Hirschberg's idea: compute LCS length in O(n) space at midpoint of s1,
# recurse on left and right halves. O(mn) time, O(n) space + reconstruction.
# For interview: mention the trade-off
# 'I can reduce to O(n) space if only the value is needed.
# To also reconstruct the sequence, I need the full O(mn) table
# or a more complex divide-and-conquer approach.'
print('Space opt: O(n) for length only')
print('Full table: O(mn) needed for reconstruction')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: 2D DP tables can be compressed to O(n) space using a rolling 1D array when only the previous row is needed, the diagonal variable pattern (save temp before overwriting) handles recurrences that need dp[i-1][j-1], and 0/1 knapsack iterates capacity in reverse while unbounded knapsack iterates forward. Next up we study the Backtracking template: Choose, Explore, Unchoose — the foundation of exhaustive search algorithms.
Frequently asked questions
Is the “Space Optimisation for 2D DP” lesson free?
Yes — the full text of “Space Optimisation for 2D DP” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Space Optimisation for 2D DP” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP