Lines as Candidates

The Wall We Hit in Chapter 2

The monotonic queue optimized DP where the cost was separable. The recurrence looked like:

dp[i] = min(dp[j]) + cost[i]    for j in some sliding window

The key property: the thing inside the min depended only on j, and the thing outside depended only on i. You could factor them apart. The queue tracked the j-part, and you bolted on the i-part afterwards.

But what if the cost depends on BOTH i and j?

dp[i] = min(dp[j] + A[j] * B[i])    for all valid j < i

You can't separate this. The term A[j] * B[i] ties i and j together. The best j for one value of i might not be the best j for a different value of i. The monotonic queue can't handle that.

This is where the Convex Hull Trick enters.

Every Candidate Is a Line

Here's the key rewrite. For a fixed j, the expression dp[j] + A[j] * B[i] is a function of B[i]. If we let x = B[i], then:

f_j(x) = A[j] * x + dp[j]

That's a linear function. Slope is A[j], intercept is dp[j].

Each candidate j defines a line. When we want to compute dp[i], we're evaluating ALL these lines at the point x = B[i] and taking the minimum.

Read that again. Each candidate j gives you a line. You query that collection of lines at a specific x value. The answer is the smallest y value across all lines at that x.

This is a geometry problem now.

The Lower Envelope

If you plot all the candidate lines on the xy-plane, you get a mess of intersecting lines. But we only care about the minimum at each x value. Trace your finger along the bottom-most line at every point from left to right. The curve you trace is called the lower envelope.

The lower envelope is piecewise linear. Each piece belongs to one of the original lines. As you move right, the "winning" line changes at specific breakpoints — the intersection points of adjacent lines in the envelope.

y ^
  │                   ╱ L3 (m=1, b=8)   — shallowest, starts highest
  │                 ╱ ╱
  │               ╱ ╱ L2 (m=3, b=4)     — medium
  │             ╱ ╱ ╱
  │           ╱ ╱ ╱ L1 (m=5, b=1)       — steepest, starts lowest
  │         ╱ ╱ ╱
  │       ╱ ╱ ╱
  │     ╱ ╱ ╱
  │   ╱─╱─╱──────────────────────────── ← lower envelope (minimum)
  │         │           │
  │  L1     │    L2     │     L3
  │  wins   │   wins    │    wins
  └─────────┴───────────┴─────────────> x
           x₁₂         x₂₃
       (L1 & L2      (L2 & L3
       intersect)    intersect)

The lower envelope is the "floor" — the bottom boundary of all the lines. Only lines that appear on this floor matter. Lines that are completely above some other line at every point are irrelevant. They've been eclipsed.

Lower envelope — multiple lines plotted on a coordinate plane, with the piecewise minimum traced in bold showing which line is optimal at each x

Why a Stack Works

Here's where the monotonic stack connection becomes clear.

Suppose the lines are added in order of decreasing slope. The first line is the steepest, the second is slightly less steep, and so on. This happens naturally in many DP problems when A[j] is monotonically decreasing as j increases.

Think about what decreasing slope means geometrically. A steep line dominates on the left (small x), and a shallow line dominates on the right (large x). When you add a new line with a shallower slope than everything on the stack, that line WILL eventually become the minimum as x goes far enough to the right.

So every new line must join the envelope. It's always pushed.

But here's the thing: the new line might make some existing lines irrelevant. A line that was part of the envelope might now be completely above the new line and the line below it. It's been squeezed out. Eclipsed. Just like in the monotonic stack, where a new larger element causes smaller elements to pop.

And which lines get eclipsed? The ones at the TOP of the stack — the most recently added, shallowest-slope lines. You peel them off from the top until the envelope is valid again.

Last in, first out. It's a stack.

The Parallel

Let's make this explicit, because the mapping between 1D monotonic stack and 2D geometry is the core idea of this chapter.

1D Array (NGE)	2D Geometry (Lower Envelope)
Stack holds indices	Stack holds lines
New element eclipses smaller elements	New line eclipses dominated lines
Pop: element can never be the answer again	Pop: line is never the minimum again
Push: new element joins the chain	Push: new line joins the envelope
Decreasing chain invariant	Increasing intersection x-coordinates
O(N) amortized	O(N) amortized

The invariant changes form. In NGE, the stack values were decreasing. Here, the intersection x-coordinates of consecutive lines in the envelope must be strictly increasing. That's the geometric version of the chain invariant.

If a new line causes the intersection sequence to go backwards — if the new intersection happens BEFORE the previous one — then the top line is eclipsed and gets popped. Same logic, different geometry.

1D stack (eclipsed element) vs 2D geometry (eclipsed line) — the same principle in two settings

Sorted Queries: The Pointer Trick

There's a bonus when queries are also sorted. If we query the envelope at increasing x values (which happens when B[i] increases with i), we never need to go backwards on the envelope.

As x increases, the winning line can only move forward through the envelope. The first line wins for a while, then the second, then the third. Once a line stops winning, it never wins again for larger x.

This means we can walk a pointer forward along the envelope. For each query, advance the pointer while the next line gives a smaller value. No binary search needed.

With sorted slopes AND sorted queries, the entire algorithm is O(N) — linear, just like the basic monotonic stack.

If the queries aren't sorted, you'd need binary search on the envelope to find the winning line, giving O(N log N). But the sorted case is the sweet spot.

Putting It Together

Here's the full picture for the sorted case:

Process lines in decreasing slope order.
For each new line, pop the stack while the top line is eclipsed (we'll define the exact condition in the next lesson).
Push the new line.
Walk a pointer across the envelope to answer queries in increasing x order.

// Build the envelope
deque<Line> hull;
for (auto& line : lines) {
    while (hull.size() >= 2 && eclipsed(hull.end()[-2], hull.back(), line))
        hull.pop_back();
    hull.push_back(line);
}

// Answer sorted queries
int ptr = 0;
for (long long x : queries) {
    while (ptr + 1 < hull.size() && hull[ptr + 1].eval(x) <= hull[ptr].eval(x))
        ptr++;
    cout << hull[ptr].eval(x) << "\n";
}

The eclipsed function is doing all the heavy lifting. It decides whether the top line should be popped. That's the subject of the next lesson, where we'll derive the intersection formula and the exact pop condition.

Why This Matters for DP

Let's come back to the DP motivation. You have:

dp[i] = min over j < i of (dp[j] + A[j] * B[i])

Each j gives a line: slope = A[j], intercept = dp[j]. You query at x = B[i].

If A[j] is decreasing in j, the lines are added in decreasing slope order — perfect for our stack.

If B[i] is increasing in i, the queries are in increasing x order — perfect for the pointer trick.

When both conditions hold, the entire DP goes from O(N^2) to O(N). That's the power of the Convex Hull Trick: it turns a quadratic DP into a linear one by recognizing that the candidates form a set of lines, and the monotonic stack maintains their lower envelope.

Try It

The starter code reads N lines (slope and intercept pairs, sorted by decreasing slope) and Q queries (x values, sorted in increasing order). Your job: build the lower envelope and answer each query with the minimum y value.

Don't worry about getting the eclipse condition perfect yet — the next lesson covers that in detail. For now, try implementing the query pointer that walks forward. If you skip the eclipse step, the envelope will have too many lines but still give correct answers (just slower).

Input format: Line 1: N Q Next N lines: m_i c_i (slope and intercept, in decreasing slope order) Next Q lines: x_i (query points, in increasing order)

Output: For each query, print the minimum value across all lines at that x.

Example:

Lines: y = 5x + 1, y = 3x + 4, y = x + 8. At x = 0: min(1, 4, 8) = 1. At x = 2: min(11, 10, 10) = 10. At x = 4: min(21, 16, 12) = 12. At x = 6: min(31, 22, 14) = 14.

Expected output: