SMAWK Algorithm

Purpose: Find the row minima of an $n\times m$ totally monotone matrix in $O(n+m)$ — without ever reading most of the matrix. Named for its five authors: Aggarwal, Klawe, Moran, Shor, Wilber.

Totally monotone matrices

A matrix $A$ is totally monotone (for row minima) if for all $i<j$ and $k<l$:

$A[i][l]\le A[i][k]⟹A[j][l]\le A[j][k].$

In words: once a later column becomes at least as good in some row, it stays at least as good in every lower row. This implies the argmin positions are non-decreasing down the rows:

$\mathrm{opt}(1)\le \mathrm{opt}(2)\le \cdots \le \mathrm{opt}(n).$

Any matrix satisfying the quadrangle inequality (the concave/convex Monge condition)

$A[i][k]+A[j][l]\le A[i][l]+A[j][k](i<j,k<l)$

is totally monotone. Monge matrices arise constantly in DP: costs of the form $w(i,j)$ with a concave or convex structure, distances in trees, and many “cost of merging a range” functions.

Algorithm

Two mutually recursive procedures:

• REDUCE. If $m>n$, discard columns that cannot contain any row minimum. Use a stack: compare the top column against the current one at row $|\text{stack}|$; total monotonicity lets each comparison either pop a column permanently or advance. Result: $m\le n$ columns remain, in $O(m)$ comparisons.
• SMAWK. Recurse on the even-indexed rows only. That gives the argmins for half the rows. The odd rows’ argmins are then sandwiched between their neighbours’ argmins, so a single linear scan fills them in.

$T(n,m)=T(n/2,n)+O(n+m)\Rightarrow O(n+m).$

Complexity

• Time: $O(n+m)$ matrix accesses — optimal, since you must at least read one entry per row
• Space: $O(n+m)$
• Requirement: entries must be computable in $O(1)$ on demand (the matrix is never materialised)

The optimization ladder for DP

SMAWK is the strongest member of a family:

Recurrence	Condition	Technique	Time
$dp[i]={\min }_j(dp[j]+w(j,i))$	none	brute force	$O(n^2)$
same	$w$ convex/concave Monge	D&C DP	$O(n\log n)$
same	$w$ Monge, offline	SMAWK	$O(n)$
same	$w$ Monge, online (values depend on earlier answers)	LARSCH / “SMAWK online”	$O(n)$
$dp[i]={\min }_j(dp[j]+b_j{x}_i)$	linear in $x$	CHT	$O(n)$ or $O(n\log n)$
$dp[i][j]={\min }_k(dp[i][k]+dp[k][j])+C$	quadrangle inequality	Knuth	$O(n^2)$

The online problem

Plain SMAWK requires the matrix entries to be available on demand — but in a 1D/1D DP, $A[i][j]$ depends on $dp[j]$, which is itself being computed. The LARSCH algorithm (Larmore-Schieber) handles this online case in $O(n)$. In a contest, D&C DP at $O(n\log n)$ is nearly always sufficient and far easier.

Applications

• Least-weight subsequence / line breaking — the classic Knuth-Plass text justification problem
• Concave least-weight subsequence — optimal paragraph and page breaking
• All-pairs shortest paths in Monge graphs, RNA secondary structure prediction
• Largest empty rectangle, optimal binary search trees with Monge costs
• Row minima of a distance matrix in a convex polygon

Variants / Use Cases

• Divide and Conquer DP — the $O(n\log n)$ version you should write
• Knuth optimization — the interval-DP cousin
• Yao optimization — the quadrangle inequality conditions in general
• Dynamic Programming — the branch overview