Max Value of Equation
Last Updated: March 29, 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.
Here's the critical insight that unlocks this problem. Since the points are sorted by x-coordinate and i < j, we know xj >= xi, so |xi - xj| = xj - xi. That means our equation simplifies to:
yi + yj + xj - xi = (yi - xi) + (yj + xj)
This decomposition is everything. For a fixed point j, the value (yj + xj) is a constant. So we need to find 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's a sliding window maximum problem.
Key Constraints:
points.length <= 10^5-- With up to 100,000 points, we need O(n log n) or O(n). An O(n^2) brute force checking all pairs won't pass.-10^8 <= xi, yi <= 10^8-- Large coordinate values mean we needlongin Java and similar care to avoid overflow.- Points are sorted by x-coordinate -- This is a gift. We don't 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-- k can be very large (up to the full x-range), so worst case every point is a candidate for every other point.
Approach 1: Brute Force
Intuition
The most direct approach: 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 further points will also exceed k (because x is strictly increasing). So for each j, we can scan backwards from j-1 until we find a point where the distance exceeds k.
Algorithm
- Initialize
resultto negative infinity. - 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
resultif this value is larger. - Return
result.
Example Walkthrough
Input:
Check all valid pairs (where x-distance ≤ k = 1):
- Pair ([1,3], [2,0]): 3 + 0 + |1-2| = 4
- Pair ([5,10], [6,-10]): 10 + (-10) + |5-6| = 1
Output:
Code
- Time Complexity: O(n^2). In the worst case (when k is large enough that all points are within distance k of each other), the inner loop runs O(n) times for each outer iteration, giving O(n^2) total.
- Space Complexity: O(1). We only use a few variables to track the result.
For each point j, we scan backwards through all points within distance k to find the best partner. The equation decomposes into (yi - xi) + (yj + xj), so for each j, we just need the maximum (yi - xi) within a sliding window. What if we maintained that maximum efficiently?
Approach 2: Priority Queue (Max-Heap)
Intuition
From our decomposition, for each point j, we want the maximum (yi - xi) among all points i where xj - xi <= k. A max-heap is a natural fit. We push (yi - xi, xi) for each point. When processing point j, we pop entries from the heap whose x-coordinate is too far from xj (distance > k). The top of the heap then gives us the best candidate.
The key difference from a deque approach: a heap can't remove arbitrary elements efficiently, so we use lazy deletion. We just pop expired entries from the top when we encounter them.
Algorithm
- Initialize a max-heap (priority queue) and
resultto negative infinity. - 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 updateresult. - Push
(yj - xj, xj)onto the heap for future points to consider. - Return
result.
Example Walkthrough
Code
- Time Complexity: O(n log n). Each point is pushed onto the heap once (O(log n)) and popped at most once (O(log n)). So across all n points, we do O(n log n) work.
- Space Complexity: O(n). The heap can hold up to n entries.
The heap maintains a full ordering of all elements, but we only ever need the maximum. What if we could find the maximum in O(1) and maintain it in O(1) amortized as elements enter and leave the window?
Approach 3: Monotonic Deque (Optimal)
Intuition
Here's the core observation again: the equation yi + yj + |xi - xj| simplifies to (yi - xi) + (yj + xj) because points are sorted by x. For each point j, we want to maximize (yi - xi) among all previous points i where xj - xi <= k.
A monotonic deque (decreasing) is the perfect tool. It maintains candidates in decreasing order of (yi - xi). The front of the deque always holds the best candidate. When the front becomes too far away (distance > k), we pop it. When a new point has a (yi - xi) value that's better than entries at the back, those entries are dominated and can be removed.
The monotonic deque exploits a dominance property. Suppose we have two candidate points A and B where A was added before B (so A has a smaller x-coordinate). If (yA - xA) <= (yB - xB), then B is strictly better than A for every future point j, because: (1) B has a higher or equal (yi - xi) value, giving a better equation result. (2) B has a larger x-coordinate, so it stays valid in the window longer. A is dominated on both dimensions, so it can never be the optimal choice.
Algorithm
- Initialize a deque and
resultto negative infinity. - 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 updateresult. - 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. - Return
result.
Example Walkthrough
Code
- Time Complexity: O(n). Each point is pushed to the deque once and popped at most once. All deque operations (push/pop from either end) are O(1). The total work across all iterations is O(n).
- Space Complexity: O(n). The deque can hold at most n entries in the worst case.