Slope Trick

Why Slope Trick Matters

Dynamic programming problems over continuous domain variables or large integer ranges often involve state transitions of the form $dp_i(x) = \min_y \{ dp_{i-1}(y) + \text{cost}(x, y) \}$. When the domain of $x$ is large (e.g., $10^9$), standard array-based dynamic programming fails due to memory and time constraints. Even coordinate compression becomes unusable when the transition cost function depends dynamically on continuous distance metrics, such as $ x - a_i|$.

Slope Trick is a data structure technique that optimizes dynamic programming algorithms where the state function $f(x)$ is continuous, piecewise-linear, and convex. Instead of evaluating $f(x)$ at discrete points, Slope Trick maintains $f(x)$ implicitly by tracking its minimum value $min\_f$ alongside two multisets of "knots" (change points) where the slope of $f(x)$ increases or decreases by $1$. Using max-heaps and min-heaps to represent these knots reduces complex functional transitions—such as prefix minima sweeps and function additions—to $O(\log N)$ priority queue operations.

Core Concepts and Terminology

A continuous function $f: \mathbb{R} \to \mathbb{R}$ is piecewise-linear if its domain can be partitioned into intervals over which $f(x)$ is a line segment $a x + b$. It is convex if its derivative $f'(x)$ is non-decreasing across its domain. The points where $f'(x)$ changes discretely are called knots (or slope change points).

Because $f'(x)$ changes only by integer increments in typical competitive programming and optimization tasks, any convex piecewise-linear function $f(x)$ can be uniquely identified by:

1. The minimum value of the function, $min\_f = \min_x f(x)$.
2. The interval $[L_{max}, R_{min}]$ where $f(x) = min\_f$ (the flat bottom where slope is $0$).
3. A max-heap $L$ storing all knots to the left of $L_{max}$ (where slope changes by $+1$ as we move right).
4. A min-heap $R$ storing all knots to the right of $R_{min}$ (where slope changes by $+1$ as we move right).

Formally, the function is expressed as:

$$f(x) = min\_f + \sum_{l \in L} \max(0, l - x) + \sum_{r \in R} \max(0, x - r)$$

How Slope Trick Works, Step by Step

Slope Trick maintains a convex function under three primary operations:

1. Adding an Absolute Distance Function $g(x) = \vert{}x - a\vert{}$

Adding $\vert{}x - a\vert{}$ increases the slope by $+1$ for $x > a$ and decreases the slope by $-1$ for $x \lt a$ (which is equivalent to adding a knot at $x = a$ to both $L$ and $R$).

• Case 1 ($a \lt L_{max}$): The point $a$ falls in the left region. $min\_f$ increases by $L_{max} - a$. The old $L_{max}$ is pushed to $R$, and $a$ is added twice to $L$ (so $L.top()$ becomes $a$).
• Case 2 ($a > R_{min}$): The point $a$ falls in the right region. $min\_f$ increases by $a - R_{min}$. The old $R_{min}$ is pushed to $L$, and $a$ is added twice to $R$.
• Case 3 ($L_{max} \le a \le R_{min}$): The point $a$ falls inside the minimum range. $min\_f$ remains unchanged. $a$ is added once to $L$ and once to $R$.

2. Prefix Minimum Sweep $f_{new}(x) = \min_{y \le x} f_{old}(y)$

This operation is required when enforcing non-decreasing sequence constraints ($x_i \ge x_{i-1}$).

• For all $x \ge L_{max}$, $f_{new}(x) = min\_f$ (the slope stays $0$).
• All knots to the right of $L_{max}$ are removed, meaning Right Heap $R$ is completely cleared.

The control flow for updating a non-decreasing sequence DP ($dp_i(x) = \min_{y \le x} dp_{i-1}(y) + \vert{}x - a_i\vert{}$) follows this decision process:

flowchart TD
A[Start: Next Element a_i] --> B{Check a_i vs L_max}
B -- a_i < L_max --C[Cost Increase: min_f += L_max - a_i]
C --> D[Pop L_max from Left Heap L]
D --> E[Push a_i into Left Heap L twice]
B -- a_i >= L_max --> F[No Cost Increase: min_f unchanged]
F --> G[Push a_i into Left Heap L once]
E --> H[Apply Prefix Minimum: Clear Right Heap R]
G --> H
H --> I[End: State updated for a_i]

Worked Example with a Full Trace

Consider the classic problem: Make Array Non-Decreasing with Minimum Total Absolute Modification (Codeforces 713C / LeetCode 2263).

Given array $A = [4, 1, 3, 2]$, we want to construct a non-decreasing array $B$ ($B_0 \le B_1 \le B_2 \le B_3$) minimizing $\sum_{i=0}^3 \vert{}A_i - B_i\vert{}$.

We initialize $min\_f = 0$ and an empty max-heap $L$.

Implementation in Python, C++, and Java

The following implementations compute the minimum cost to make an array non-decreasing using Slope Trick. All three programs feature identical logic, process the sample input $A = [4, 1, 3, 2]$, and produce identical terminal outputs.

import heapq

def solve_slope_trick(arr):
    # Max-heap L stored using negated values
    L = []
    min_f = 0

    for idx, x in enumerate(arr):
        if L and -L[0] > x:
            l_max = -heapq.heappop(L)
            min_f += l_max - x
            heapq.heappush(L, -x)
            heapq.heappush(L, -x)
        else:
            heapq.heappush(L, -x)

        print(f"Processing x = {x}: min_cost = {min_f}, heap top = {-L[0]}")

    print(f"\nFinal Minimum Cost: {min_f}")
    return min_f

if __name__ == "__main__":
    arr = [4, 1, 3, 2]
    solve_slope_trick(arr)

#include <iostream>
#include <vector>
#include <queue>

long long solve_slope_trick(const std::vector<long long>& arr) {
    // Max-heap L
    std::priority_queue<long long> L;
    long long min_f = 0;

    for (long long x : arr) {
        if (!L.empty() && L.top() > x) {
            long long l_max = L.top();
            L.pop();
            min_f += l_max - x;
            L.push(x);
            L.push(x);
        } else {
            L.push(x);
        }

        std::cout << "Processing x = " << x << ": min_cost = " << min_f
                  << ", heap top = " << L.top() << "\n";
    }

    std::cout << "\nFinal Minimum Cost: " << min_f << "\n";
    return min_f;
}

int main() {
    std::vector<long long> arr = {4, 1, 3, 2};
    solve_slope_trick(arr);
    return 0;
}

import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static long solveSlopeTrick(long[] arr) {
        // Max-heap L
        PriorityQueue<Long> L = new PriorityQueue<>(Collections.reverseOrder());
        long minF = 0;

        for (long x : arr) {
            if (!L.isEmpty() && L.peek() > x) {
                long lMax = L.poll();
                minF += lMax - x;
                L.add(x);
                L.add(x);
            } else {
                L.add(x);
            }

            System.out.println("Processing x = " + x + ": min_cost = " + minF
                               + ", heap top = " + L.peek());
        }

        System.out.println("\nFinal Minimum Cost: " + minF);
        return minF;
    }

    public static void main(String[] args) {
        long[] arr = {4, 1, 3, 2};
        solveSlopeTrick(arr);
    }
}

Complexity, Correctness, and Invariants

The time and space bounds of Slope Trick depend on priority queue operations over $N$ elements.

Variants, Pitfalls, and Optimizations

Slope Trick extends to several functional operations:

1. Shift / Translation $f_{new}(x) = \min_{x - b \le y \le x - a} f_{old}(y)$:

Used in inventory smoothing or bounded movement problems. This shifts all knots in $L$ by $+a$ and all knots in $R$ by $+b$. Rather than modifying every heap element, maintain lazy offset tags shift_L and shift_R. 2. Both Left and Right Slopes: When prefix minimum is not applied, $R$ is preserved. Operations require checking both $L.top()$ and $R.top()$ to determine where $a_i$ lies relative to $[L_{max}, R_{min}]$.

Practice Problems and Real-World Use

Slope Trick appears in competitive programming and production optimization tasks involving continuous inventory planning and non-decreasing transformations.