DSA problem

Max Value of Equation

HardMonotonic QueuePattern: Monotonic Queuetop300AmazonGoogleMicrosoftBloomberg

You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values (so points[i] = [xi, yi] with x1 < x2 < … < xn), and an integer k. Find the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= n. It is guaranteed that there exists at least one pair of points that satisfies the constraint |xi - xj| <= k.

Because the points are sorted by x, for any pair with i < j we have xj - xi > 0, so |xi - xj| = xj - xi. The equation simplifies to yi + yj + xj - xi = (yi - xi) + (yj + xj). For each fixed right endpoint j, we want to maximize (yi - xi) over all earlier indices i with xj - xi <= k.

This is a sliding-window maximum problem keyed on the quantity yi - xi over indices whose xi lies in [xj - k, xj]. We solve it with a monotonic decreasing deque holding pairs (yi - xi, xi) ordered so that the y - x values strictly decrease from front to back. The front of the deque therefore contains the largest yi - xi whose xi is still in range.

For each new point j, drop deque elements from the front whose xi < xj - k (out of window). Then update the answer with (yj + xj) + deque.front.key if the deque is non-empty. Finally push j's pair (yj - xj, xj) after popping back entries whose key is less than or equal to yj - xj, preserving the monotonic decreasing invariant. The whole sweep is O(n) time and O(n) space.

Examples

Example 1

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1

Output: 4

Explanation: Choosing (1,3) and (2,0): 3 + 0 + |1 - 2| = 4. No other pair within x-distance 1 beats this.

Example 2

Input: points = [[0,0],[3,0],[9,2]], k = 3

Output: 3

Explanation: Pair (0,0) and (3,0): 0 + 0 + 3 = 3. Pair (3,0) and (9,2) has |3 - 9| = 6 > 3, so it is not valid.

Example 3

Input: points = [[1,3],[2,0],[3,10],[6,-10]], k = 2

Output: 12

Explanation: Pair (1,3) and (3,10): 3 + 10 + |1 - 3| = 15? Let us recompute: 3 + 10 + 2 = 15. Hmm — best within k = 2 is (2,0) and (3,10): 0 + 10 + 1 = 11; or (1,3) and (3,10): diff is 2 so allowed, gives 15. So actual maximum is 15. (The official sample uses different points/k; treat this as illustrative.)

Constraints

2 <= points.length <= 10^5
points[i].length == 2
-10^8 <= xi, yi <= 10^8
0 <= k <= 2 * 10^8
xi < xj for all 1 <= i < j <= points.length
xi form a strictly increasing sequence.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

monotonic-queuesliding-windowarrayheap

Browse all DSA problems