Max Value of Equation

HardMonotonic Deque · Sliding Window🧩 Queue & Monotonic Deque LeetCode #1499 ↗Updated Oct 30, 2026

Problem

You get 2D points whose x-coordinates are strictly increasing, plus an integer k. Among all pairs i < j with x_j - x_i ≤ k, return the largest value of y_i + y_j + |x_i - x_j|. At least one valid pair is guaranteed to exist.

Inputpoints=[[1,3],[2,0],[5,10],[6,-10]], k=1Output4

Inputpoints=[[0,0],[3,0],[9,2]], k=3Output3

2 ≤ n ≤ 10⁵ · -10⁸ ≤ x, y ≤ 10⁸ · 0 ≤ k ≤ 2·10⁸ · x strictly increasing

Try it yourself

Java

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Because x_i < x_j, the value splits into (y_j + x_j) + (y_i - x_i). For each j you only need the maximum y - x in a sliding x-window — a monotonic deque gives it in O(1).

PatternQueue & Monotonic Deque

Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.

Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.

Open the Queue & Monotonic Deque guide →

Approaches

Brute ForceCheck Every Pair in Range

Time O(n²)Space O(1)

For each right point j, walk left over earlier points while the x-gap stays within k and evaluate the equation directly. Since x is sorted, the walk can stop at the first point that is too far away.

Java

public int findMaxValueOfEquation(int[][] points, int k) {
    int best = Integer.MIN_VALUE;
    for (int j = 1; j < points.length; j++) {
        // x is sorted, so stop once the gap exceeds k
        for (int i = j - 1; i >= 0 && points[j][0] - points[i][0] <= k; i--) {
            int value = points[i][1] + points[j][1] + points[j][0] - points[i][0];
            best = Math.max(best, value);
        }
    }
    return best;
}

Correct and simple, but quadratic when k is large (every pair is in range).

BetterMax-Heap of (y − x) with Lazy Removal

Time O(n log n)Space O(n)

Rewrite the value as (y_j+x_j) + (y_i-x_i). Keep earlier points in a max-heap keyed by y - x. Before using the top, pop entries whose x is more than k behind — they can never be valid again because x only grows.

Java

public int findMaxValueOfEquation(int[][] points, int k) {
    // heap entry: {y - x, x}, largest y - x on top
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    int best = Integer.MIN_VALUE;
    for (int[] p : points) {
        int x = p[0], y = p[1];
        while (!heap.isEmpty() && x - heap.peek()[1] > k) heap.poll(); // out of range forever
        if (!heap.isEmpty()) best = Math.max(best, heap.peek()[0] + x + y);
        heap.offer(new int[]{y - x, x});
    }
    return best;
}

Big win over pairs, but the heap costs a log factor and holds stale entries.

OptimalMonotonic Deque (Sliding Window Maximum)

Time O(n)Space O(n)

Keep indices in a deque with decreasing y - x. Drop expired points from the front, read the best partner at the front, then pop from the back every point whose y - x is not better than the new one — it is older and worse, so it can never win.

Java

public int findMaxValueOfEquation(int[][] points, int k) {
    Deque<Integer> dq = new ArrayDeque<>(); // indices, y - x decreasing front to back
    int best = Integer.MIN_VALUE;
    for (int j = 0; j < points.length; j++) {
        int x = points[j][0], y = points[j][1];
        while (!dq.isEmpty() && x - points[dq.peekFirst()][0] > k) dq.pollFirst();
        if (!dq.isEmpty()) {
            int i = dq.peekFirst();
            best = Math.max(best, points[i][1] - points[i][0] + y + x);
        }
        // older points with smaller-or-equal y - x are dominated by point j
        while (!dq.isEmpty()) {
            int last = dq.peekLast();
            if (points[last][1] - points[last][0] > y - x) break;
            dq.pollLast();
        }
        dq.offerLast(j);
    }
    return best;
}

Dry runpoints=[[1,3],[2,0],[5,10],[6,-10]], k=1

j current pointf deque front changed

y-x
2

-2

5

-16

points' y-x, k=1
j=0
2
j
-2

5

-16

dq empty, push 0
j=1
2
f
-2
j
5

-16

2+(0+2)=4, push 1
j=2
2

-2

5
j
-16

x=5: 0,1 expired
j=3
2

-2

5
f
-16
j
5+(-10+6)=1
end
2

-2

5

-16

best = 4 ✔

Each point enters and leaves the deque once — linear time, the expected answer.

Pro tip

Say the split (y_j+x_j) + (y_i-x_i) out loud — once the pair term is separable, it is “Sliding Window Maximum”.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Pair in Range	`O(n²)`	`O(1)`
Better	Max-Heap of (y − x) with Lazy Removal	`O(n log n)`	`O(n)`
Optimal	Monotonic Deque (Sliding Window Maximum)	`O(n)`	`O(n)`

Common pitfalls

Reading the answer after pushing point j — pairs it with itself.
Forgetting the window check x_j - x_i ≤ k before using the front.
Starting best at 0 — the true maximum can be negative.

Interview tips

Drop the absolute value first: sorted x means |x_i-x_j| = x_j-x_i.
Offer the heap version, then explain why a deque removes the log factor.
State the deque invariant: front is the best still-valid partner.

Pattern

Monotonic deque → max/min of a separable term over a sliding window that only moves forward.

My notes saved in this browser