Max Value of Equation
Hard · Stack & Strings · Array · Queue · Sliding Window · Heap (Priority Queue) · Monotonic Queue
Problem
You are given points, where points[i] = [x_i, y_i] is a point on the plane, sorted by x in strictly increasing order, and an integer k.
Return the largest value of y_i + y_j + |x_i - x_j| over all pairs i < j whose x-coordinates are at most k apart (|x_i - x_j| <= k). At least one such pair is guaranteed to exist.
Examples
Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1 Output: 4
Only [1,3]–[2,0] (value 3 + 0 + 1 = 4) and [5,10]–[6,-10] (value 1) are within distance 1. The best is 4.
Input: points = [[0,0],[3,0],[9,2]], k = 3 Output: 3
Only [0,0] and [3,0] are within 3 of each other: 0 + 0 + 3 = 3.
Input: points = [[-2,3],[0,0],[5,1]], k = 10 Output: 11
Every pair qualifies; [-2,3] with [5,1] gives 3 + 1 + 7 = 11.
Constraints
- 2 <= len(points) <= 10^5
- points[i].length == 2
- -10^8 <= x_i, y_i <= 10^8
- 0 <= k <= 2 · 10^8
- x_i < x_j whenever i < j
- At least one pair has |x_i − x_j| <= k.
Approaches
- Check every close pair — time O(n · w), w = points within k of each other (O(n²) worst case), space O(1)
Follow-up
A max-heap keyed by y - x also works: push each point after using it, and lazily discard heap tops that are too far left. It is simpler to get right but costs O(n log n). The deque wins because points leave the window in the same order they entered.
Related problems
Start free on Cariara · Coding problems · System design studio
