Hirschberg O(n)-Space Divide-and-Conquer Sequence Alignment & Diff

Breaking the $O(nm)$ Memory Barrier for Backtracking

Computing the numeric Levenshtein edit distance between strings of length $n$ and $m$ requires only $2 \min(n, m)$ cells of memory by keeping two rolling rows. However, recovering the actual alignment / diff transcript seems to require storing the full $n \times m$ table of parent pointers ($40\text{ GB}$ for two $100{,}000$-char files!).

Dan Hirschberg (1975) solved this in $O(n + m)$ space and $O(nm)$ time:

1. Every optimal path from $(0, 0)$ to $(n, m)$ in the DP grid must cross the middle row $i = \lfloor n/2 \rfloor$ at some column $k^ \in [0, m]$.
2. The cost of the shortest path from $(0,0)$ to $(n,m)$ passing through $(\lfloor n/2 \rfloor, k)$ is: $$\text{Cost}(k) = \text{ForwardDP}(A[0..\lfloor n/2 \rfloor),\; B[0..k)) + \text{ReverseDP}(A[\lfloor n/2 \rfloor..n),\; B[k..m))$$
3. Both terms are computed for all $k \in [0..m]$ simultaneously using two 2-row DP sweeps in $O(m)$ space!
4. Once $k^$ is found, the problem splits into two subproblems of height $n/2$ and widths $k^$ and $m - k^$.

Why Total Time Remains $O(nm)$

At depth $d$ of the recursion tree, the subproblem heights are $n / 2^d$ and their widths sum to $m$:

$$\sum_{d=0}^{\log_2 n} c \cdot \frac{n}{2^d} \cdot m = c \cdot nm \sum_{d=0}^{\infty} 2^{-d} = 2 c \cdot nm = O(nm)$$

Curriculum Connections

• Classic DP: Knapsack, LCS, LIS & Edit Distance
• DP Foundations: Optimal Substructure & DAG View
• Recurrence Relations, Master Theorem & Akra-Bazzi

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Two-Row Space-Optimized Forward & Reverse DP

• Core Mechanical Concept: Two-Row Space-Optimized Forward & Reverse DP
• Target Module: index.js (Step1)
• Engineering Specification: Implement _dpRow(a, b, reverse) using only two Int32Array(m + 1) buffers (prev and curr). When reverse === true, scan a and b from right to left to compute suffix edit distances.
• Verification Invariant: verifies Step 1: Two-Row Space-Optimized Forward & Reverse DP

Step 2: Base-Case Alignment Transcript

• Core Mechanical Concept: Base-Case Alignment Transcript
• Target Module: index.js (Step2)
• Engineering Specification: Implement _alignBase(a, b) for when |a| <= 1 or |b| <= 1, where the DP matrix has size $O(n + m)$ and can be backtracked directly.
• Verification Invariant: verifies Step 2: Base-Case Alignment Transcript

Step 3: Optimal Midpoint Split Discovery

• Core Mechanical Concept: Optimal Midpoint Split Discovery
• Target Module: index.js (Step3)
• Engineering Specification: Split a at mid = n >> 1, run forward DP on a[0..mid) and reverse DP on a[mid..n), and find the split index $k^ = \arg\min_k (\text{scoreL}[k] + \text{scoreR}[m - k])$.
• Verification Invariant: verifies Step 3: Optimal Midpoint Split Discovery

• Category: Dynamic Programming & Divide-and-Conquer
• Difficulty: Advanced (~50 minutes)
• Key Architectural Highlights:
  • Two-row rolling DP computing forward prefix costs and backward suffix costs in O(min(n, m)) memory
  • Optimal midpoint split k = argmin_k (fwd[k] + bwd[m - k]) on the middle row i = floor(n/2)
  • Master-Theorem geometric work series T(n,m) <= 2 n m achieving O(nm) time in O(n + m) total space
• Tags & Primitives: Hirschberg Algorithm, Linear Space DP, Sequence Alignment, Edit Distance, Divide and Conquer

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.