AlgoMaster Logo

Max Value of Equation

hardFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We have points on a 2D plane, sorted by their x-coordinates, and we need to find a pair of points (i, j) where j > i that maximizes yi + yj + |xi - xj|, subject to the constraint that the x-coordinates are at most k apart.

Since the points are sorted by x-coordinate and i < j, we know xj >= xi, so |xi - xj| = xj - xi. The equation simplifies to:

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

This decomposition drives every approach below. For a fixed point j, the value (yj + xj) is a constant. So we need the point i (before j, within distance k) that maximizes (yi - xi). The problem reduces to: for each j, find the maximum (yi - xi) among all valid previous points i where xj - xi <= k. That is a sliding window maximum problem.

Key Constraints

  • points.length <= 10^5. With up to 100,000 points, an O(n^2) brute force checking all pairs is on the order of 10^10 operations and times out. The target is O(n log n) or O(n).
  • -10^8 <= xi, yi <= 10^8. The largest possible equation value is yi + yj + (xj - xi), bounded by 10^8 + 10^8 + (10^8 - (-10^8)) = 4 * 10^8, which fits in a signed 32-bit integer (max ~2.1 * 10^9). So int is safe; no long is required.
  • Points are already sorted by x-coordinate. We do not need to sort, and we can process points left to right, treating earlier points as candidates for the "i" in our pair.
  • 0 <= k <= 2 * 10^8. With k large enough to span the full x-range, every earlier point can be a valid candidate, so the window can hold all n points at once.

Approach 1: Brute Force

Intuition

Check every valid pair of points. For each pair (i, j) where j > i and xj - xi <= k, compute the equation value and track the maximum.

Since the points are sorted by x-coordinate, once the x-difference exceeds k, all earlier points exceed it too (x is strictly increasing). So for each j, we scan backwards from j-1 and stop at the first point whose distance exceeds k.

Algorithm

  1. Initialize result to negative infinity.
  2. For each point j from 1 to n-1:
    • For each point i from j-1 down to 0:
      • If xj - xi > k, break (all earlier points are even farther away).
      • Compute yi + yj + xj - xi.
      • Update result if this value is larger.
  3. Return result.

Example Walkthrough

Input:

0
1
0
1
3
1
2
0
2
5
10
3
6
-10
points

With k = 1, for each j we scan backwards and stop once the x-distance exceeds 1:

  • j=1 (point [2,0]): i=0 has x-distance 2-1=1 ≤ 1. value = 3 + 0 + (2-1) = 4. result = 4.
  • j=2 (point [5,10]): i=1 has x-distance 5-2=3 > 1, so we stop immediately. No valid pair.
  • j=3 (point [6,-10]): i=2 has x-distance 6-5=1 ≤ 1. value = 10 + (-10) + (6-5) = 1. result stays 4.

The maximum across all pairs is 4.

Output:

4
result

Code

This recomputes the scan from scratch for every j. Since the equation decomposes into (yi - xi) + (yj + xj), each j only needs the maximum (yi - xi) within its window. The next two approaches maintain that running maximum instead of rescanning.

Approach 2: Priority Queue (Max-Heap)

Intuition

For each point j, we want the maximum (yi - xi) among all points i where xj - xi <= k. A max-heap keyed on (yi - xi) keeps that maximum at the top. We push (yi - xi, xi) for each point. When processing point j, we pop entries whose x-coordinate is too far from xj (distance > k), then read the top.

Expired entries can sit anywhere inside the heap, and a heap cannot remove an arbitrary interior element in O(log n). The fix is lazy deletion: an expired entry is removed only if it surfaces at the top. While it stays buried, it cannot be the maximum and never affects the answer, so leaving it in place is safe.

Algorithm

  1. Initialize a max-heap (priority queue) and result to negative infinity.
  2. For each point j from 0 to n-1:
    • Remove entries from the heap top where xj - xi > k (they're too far away).
    • If the heap is non-empty, compute heap.top() + (yj + xj) and update result.
    • Push (yj - xj, xj) onto the heap for future points to consider.
  3. Return result.

Example Walkthrough

1j=0: point [1,3]. Heap empty, no pair. Push (y-x=2, x=1)
0
1
0
1
j=0
3
j=0
1
2
0
2
5
10
3
6
-10
1/5

Code

The heap maintains a full ordering of all elements, but only the maximum is ever read. The next approach drops the ordering and keeps only the candidates that could still become the maximum, which brings the work down to O(n).

Approach 3: Monotonic Deque (Optimal)

Intuition

A monotonic deque (decreasing) holds candidate points in decreasing order of (yi - xi), so the front is always the current maximum. Each point enters and leaves the deque at most once, which makes every operation O(1) amortized and the whole algorithm O(n).

Two removals keep the invariant. From the front, drop points whose x-distance to the current point exceeds k, since they have left the window. From the back, drop points whose (yi - xi) is less than or equal to the new point's value, since they are dominated (explained below). The remaining points stay sorted by (yi - xi) from front to back.

Algorithm

  1. Initialize a deque and result to negative infinity.
  2. For each point j from 0 to n-1:
    • Remove entries from the front of the deque where xj - xi > k (expired entries).
    • If the deque is non-empty, compute front's (yi - xi) + (yj + xj) and update result.
    • Remove entries from the back of the deque where (yi - xi) is less than or equal to (yj - xj) (dominated entries).
    • Push (yj - xj, xj) to the back of the deque.
  3. Return result.

Example Walkthrough

1j=0: point [1,3]. Deque empty, no pair. Push (val=2, x=1)
0
1
0
1
j=0
3
j=0
1
2
0
2
5
10
3
6
-10
1/5

Code