Dynamic Programming Space Optimization and Interview Strategy

Suppose a text-matching feature compares two strings of 2,000 characters each. The edit-distance table from the previous lesson has 2,001 x 2,001 cells, more than four million integers, to produce one number. Look at how the recurrence reads: row i only ever looks at row i-1 and itself. Every earlier row is dead weight once the next one is finished. Space optimisation is the act of noticing that and throwing those rows away.

Keeping only the rows you still need

When a cell depends on the previous row and cells to its left in the current row, two rows are enough: prev and cur. After finishing a row, prev becomes cur and you start a new cur. The answer is the last cell of the final row. Here is the edit distance rewritten that way, checked against the full-table version on a few inputs.

def edit_distance_two_rows(a, b):
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]

def edit_distance_full(a, b):
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        d[i][0] = i
    for j in range(len(b) + 1):
        d[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1])
    return d[-1][-1]

pairs = [("PARCEL", "PRACEL"), ("kitchen-sink", "kitchen-sync"),
         ("", "abc"), ("locker-42", "locker-420")]
for a, b in pairs:
    print(repr(a), repr(b), edit_distance_two_rows(a, b), edit_distance_full(a, b))
print("cells for 2000 x 2000:", 2001 * 2001, "vs", 2 * 2001)

'PARCEL' 'PRACEL' 2 2
'kitchen-sink' 'kitchen-sync' 2 2
'' 'abc' 3 3
'locker-42' 'locker-420' 1 1
cells for 2000 x 2000: 4004001 vs 4002

Memory drops from 4,004,001 cells to 4,002 while the time stays the same. The price is that you can no longer walk back through the table to reconstruct the edit script. If the interviewer asks for the actual operations, you keep the full table (or use a more advanced divide-and-conquer technique). State that trade-off out loud.

Collapsing knapsack to one row, and the loop-direction trap

In knapsack, row i reads row[cap - w] from row i-1. If you keep a single array and update it in place, you must make sure that the cell you read has not yet been overwritten by the current item. Looping capacity from high to low guarantees that: cells to the left are still old. Looping low to high lets a cell read a value that already includes the current item, so the item gets used more than once and the problem silently becomes a different one (unbounded knapsack).

def knap_1d(items, capacity):
    row = [0] * (capacity + 1)
    for w, v in items:
        for cap in range(capacity, w - 1, -1):      # backwards keeps item single-use
            row[cap] = max(row[cap], row[cap - w] + v)
    return row[capacity]

def knap_1d_forward(items, capacity):
    row = [0] * (capacity + 1)
    for w, v in items:
        for cap in range(w, capacity + 1):          # forwards lets items repeat
            row[cap] = max(row[cap], row[cap - w] + v)
    return row[capacity]

items = [(5, 10), (3, 7)]        # (weight, value)
print("backward:", knap_1d(items, 10))
print("forward :", knap_1d_forward(items, 10))

backward: 17
forward : 21

The correct answer is 17 (one 5 kg item and one 3 kg item). The forward loop reports 21 because it packs the 3 kg item three times. The code runs, returns an integer and looks reasonable, which is why this bug survives code review. It is also precisely the behaviour you want for unbounded knapsack, where items can repeat, so you can remember the rule: backwards for single-use, forwards for reusable.

import random
from itertools import combinations

def brute_knap(items, capacity):
    best = 0
    for r in range(len(items) + 1):
        for combo in combinations(items, r):
            if sum(w for w, _ in combo) <= capacity:
                best = max(best, sum(v for _, v in combo))
    return best

def knap_1d(items, capacity):
    row = [0] * (capacity + 1)
    for w, v in items:
        for cap in range(capacity, w - 1, -1):
            row[cap] = max(row[cap], row[cap - w] + v)
    return row[capacity]

random.seed(7)
for _ in range(500):
    its = [(random.randint(1, 9), random.randint(1, 30))
           for _ in range(random.randint(0, 7))]
    cap = random.randint(0, 25)
    assert knap_1d(its, cap) == brute_knap(its, cap), (its, cap)
print("500 random cases agree")

500 random cases agree

A practical rule for deciding whether a table can shrink: write down, for the cell [i][j], every cell it reads. If all of those sit in row i or row i-1, two rows suffice. If they also reach back to row i-2, keep three. If they reach column j+1 in the previous row, as some grid-path problems do, check the loop direction before collapsing to one array. This habit turns "I think I can save memory" into a statement you can defend line by line.

A spoken framework for DP in an interview

Interviewers are rarely testing whether you remember a particular table. They are watching whether you can move from a vague problem to a precise recurrence. This sequence works for almost any DP question and keeps you talking about reasoning rather than syntax.

1. RESTATE   "We want the (min / count / max) of ..."
2. BRUTE     "Brute force tries every choice at each step:
              that is a tree with branching b and depth d."
3. REPEAT    "Here the same sub-question appears twice:
              <name two paths that reach the same state>."
4. STATE     "A subproblem is defined by <params>. dp[x] means
              <one sentence in plain words>."
5. RECURRENCE "dp[x] = combine(dp[smaller states])"
6. BASE      "The smallest cases are ... ; unreachable = INF."
7. ORDER     "Each cell depends on ..., so I fill ... first."
8. COST      "States x work per state = time; table = space."
9. IMPROVE   "Only the previous row is needed, so O(width)
              space, at the cost of losing reconstruction."
10. TEST     "Check a tiny case by hand, then compare with
              brute force on random small inputs."

Step 4 is where candidates win or lose. Saying "dp[i][j] is the edit distance between the first i characters of A and the first j characters of B" in plain words makes the recurrence almost forced. Candidates who skip it and start typing nested loops tend to get tangled in off-by-ones they cannot explain.

Common mistakes and the symptoms they cause

• Optimising before it is correct. Starting with a one-row version means you cannot compare to anything; the symptom is an answer that is off by a small amount with no reference to debug against. Get the full table right first.
• Overwriting a value you still need. A two-dimensional recurrence that reads the diagonal (prev[j-1]) breaks if you update a single row left to right without saving the old value; results drift by one on inputs where characters match.
• Claiming a wrong complexity. Saying knapsack is O(n log n) or "polynomial in the input size". Say O(n x W), pseudo-polynomial, when asked.
• Reaching for DP when greedy or sorting suffices. If a simple sort-and-scan passes your small counter-examples, DP is unnecessary complexity; justify the choice either way.

How this shows up in real projects and interviews

In production, memory limits make rolling rows matter for string diffing and sequence alignment on long inputs, while many real problems are small enough that the readable memoised version is the right call. In interviews, expect the follow-up "can you reduce the space?" immediately after you solve a 2D problem. Mentioning in your first answer that you know it is possible, and what you would lose by doing it, tends to land better than racing to implement it. Practise by taking each solved problem from this course and writing the one-row version plus a brute-force test.

If you want more sequence and string problems to practise on, work through Arrays and Strings, and revisit the classic problems lesson to rewrite each solution with the optimisation from this one.