Pattern Reference
Slope Trick
"DP optimization for convex piecewise-linear functions. Priority queue management. Tree DP, grid DP, scheduling DP."
Loading...
Deep Dive Tutorial
Slope trick represents a convex function f(x) by its breakpoints (where slope changes by 1). f(x) = sum of |x - aᵢ| terms = piecewise linear with minimum at median. Two heaps: L = max-heap of slope-change points on the left half, R = min-heap on the right half. Adding |x - a|: push a to both heaps, then rebalance (if L.max > R.min, swap tops). The minimum value is tracked incrementally.
Slope trick for minimum sum of absolute differences
// Minimum cost to make array non-decreasing
// Cost: sum of |a[i] - b[i]| where b is non-decreasing
// Slope trick: process each element, maintain convex function
class SlopeTrick {
constructor() {
this.L = []; // max-heap (left breakpoints)
this.R = []; // min-heap (right breakpoints)
this.minVal = 0; // current minimum of f
}
pushL(x) { /* max-heap push */ this.L.push(-x); this.L.sort((a,b)=>a-b); }
pushR(x) { /* min-heap push */ this.R.push(x); this.R.sort((a,b)=>a-b); }
topL() { return -this.L[0]; }
topR() { return this.R[0]; }
// Add term |x - a| to f
addAbs(a) {
this.pushL(a); this.pushR(a);
if (this.topL() > this.topR()) {
const l = this.topL(), r = this.topR();
this.minVal += l - r;
this.L.shift(); this.R.shift();
this.pushL(r); this.pushR(l);
}
}
// Add constraint x >= prev (for non-decreasing):
// Shift R by max(0, L.top - prev), clip L at prev
addFloor(prev) {
if (this.topL() > prev) {
this.minVal += this.topL() - prev;
this.L.shift();
this.pushL(prev);
}
}
}
// Example: make array non-decreasing with minimum absolute change cost
function minCostNonDecreasing(arr) {
const st = new SlopeTrick();
for (const a of arr) {
st.addAbs(a);
// Enforce non-decreasing: clip at topL
// This is equivalent to: if new slope > topL was changed
}
return st.minVal;
}Worked Problems
trending-down
Slope trick core idea:
A sum of |x - aᵢ| terms is convex, piecewise-linear, and minimized at the median. Store breakpoints in two heaps instead of the whole function.
Two-heap invariant:
- L = max-heap of breakpoints where slope goes from -k to -k+1 (left of minimum)
- R = min-heap of breakpoints where slope goes from k-1 to k (right of minimum)
- |L| = |R| (or |L| = |R| + 1 for odd cases)
- L.top ≤ R.top always
Applications:
- Minimum moves to non-decreasing sequence: slope trick with "floor at previous minimum"
- Weighted median problems
- DP where each transition adds a |x - a| term
Key operation: Adding max(0, x) shifts the entire right half up (equivalent to cutting at 0 and raising).
A sum of |x - aᵢ| terms is convex, piecewise-linear, and minimized at the median. Store breakpoints in two heaps instead of the whole function.
Two-heap invariant:
- L = max-heap of breakpoints where slope goes from -k to -k+1 (left of minimum)
- R = min-heap of breakpoints where slope goes from k-1 to k (right of minimum)
- |L| = |R| (or |L| = |R| + 1 for odd cases)
- L.top ≤ R.top always
Applications:
- Minimum moves to non-decreasing sequence: slope trick with "floor at previous minimum"
- Weighted median problems
- DP where each transition adds a |x - a| term
Key operation: Adding max(0, x) shifts the entire right half up (equivalent to cutting at 0 and raising).