Max Value of Equation: Monotone Deque Optimization

Given an array of points sorted by their x-coordinates and an integer k, find the maximum value of yi + yj + |xi - xj| where |xi - xj| <= k. This is LeetCode 1499: Max Value of Equation, a hard problem that becomes clean once you see the algebraic trick.

Why this problem matters

This problem is the canonical example of the "monotone deque for sliding window optimization" pattern. You will see this technique in dynamic programming optimization (the "deque trick"), in problems like Shortest Subarray with Sum at Least K, and in Constrained Subsequence Sum. If you master the deque manipulation here, you unlock an entire family of hard problems.

The key insight

Since the points are sorted by x-coordinate, we know xj >= xi for any j > i. That means |xi - xj| = xj - xi. The equation becomes:

yi + yj + (xj - xi) = (yj + xj) + (yi - xi)

For a fixed point j, the term (yj + xj) is a constant. To maximize the whole expression, you want to find the largest (yi - xi) among all valid candidates i where xj - xi <= k.

This is a sliding window maximum problem. You need the maximum of (yi - xi) over a window of points whose x-distance from the current point is at most k. A monotone deque gives you that maximum in amortized O(1) per element.

The solution

from collections import deque

def find_max_value_of_equation(points, k):
    dq = deque()
    ans = float('-inf')

    for xj, yj in points:
        while dq and xj - dq[0][1] > k:
            dq.popleft()

        if dq:
            ans = max(ans, yj + xj + dq[0][0])

        val = yj - xj
        while dq and dq[-1][0] <= val:
            dq.pop()

        dq.append((val, xj))

    return ans

The deque stores tuples of (yi - xi, xi). The front always holds the maximum yi - xi value among candidates still within distance k. When processing a new point (xj, yj), you first remove expired entries from the front, then check if the front gives a better answer, and finally maintain the decreasing order by popping smaller entries from the back before appending.

Visual walkthrough

Notice how the deque shrinks aggressively. When a point with a large y - x value enters, it removes all weaker entries from the back (they will never be optimal since the new point is both better and newer). When the window slides past a point, it gets removed from the front.

Complexity analysis

The deque solution is O(n) because each point is pushed and popped at most once from each end. The total number of push and pop operations across the entire iteration is at most 2n.

The max heap approach also works: push (yi - xi, xi) into a max heap, and for each j, pop entries from the top until the front is valid. This is O(n log n) due to heap operations. The deque removes the log factor by exploiting the monotonicity constraint.

The building blocks

1. Equation reformulation

val = yi + yj + abs(xi - xj)
val = (yj + xj) + (yi - xi)

Since points are sorted by x, the absolute value disappears. Separating terms into "what depends on j" and "what depends on i" reveals the sliding window maximum structure.

2. Monotone deque maintenance

val = yj - xj
while dq and dq[-1][0] <= val:
    dq.pop()
dq.append((val, xj))

The back-pop loop ensures the deque stays in decreasing order. Any entry at the back that is less than or equal to the new value is dominated: the new entry has the same or better y - x value and a newer x-coordinate (so it will expire later). These dominated entries can never be the answer for any future j.

Edge cases

• All points at the same x-coordinate: every pair has |xi - xj| = 0, which satisfies any k >= 0. The deque still works correctly since no entries ever expire.
• k = 0: only points sharing the same x-coordinate can pair. The deque front will only be valid when xj - xi = 0.
• Negative y-values everywhere: the answer can be negative. Initialize ans to negative infinity, not zero.
• Only two points: both enter the deque, and you get one comparison. The formula still applies.
• Large gaps between x-values: many entries expire at once. The front-pop loop handles bulk removals.

From understanding to recall

You have seen the algebraic rewrite and the deque maintenance. The pattern is: reformulate an optimization over pairs into a "fixed part + sliding window maximum" structure, then use a monotone deque to track that maximum efficiently. The tricky parts under pressure are remembering what to store in the deque (both the value and the x-coordinate for expiry checks) and getting the comparison directions right (decreasing from front to back, pop back when the new entry is better).

Spaced repetition locks this in. Writing the deque maintenance loop from scratch at increasing intervals builds the recall you need to deploy this technique instantly on related problems.

Related posts

• Sliding Window Maximum - The pure monotone deque problem without the algebraic reformulation step
• Shortest Subarray with Sum at Least K - Uses the same deque-based sliding window on prefix sums
• Constrained Subsequence Sum - DP optimization with a monotone deque to track the best prior state

The deque-based sliding window optimization appears in many hard problems disguised by different contexts. Once you recognize the "maximize/minimize something over a bounded window" structure, the deque approach applies directly. CodeBricks isolates this building block so you practice the deque loop itself, independent of the problem dressing.