Watch 9 video solutions for Max Value of Equation, a hard level problem involving Array, Queue, Sliding Window. This walkthrough by Fraz has 14,380 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [xi, yi] such that xi < xj for all 1 <= i < j <= points.length. You are also given an integer k.
Return the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length.
It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi - xj| <= k.
Example 1:
Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1 Output: 4 Explanation: The first two points satisfy the condition |xi - xj| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1. No other pairs satisfy the condition, so we return the max of 4 and 1.
Example 2:
Input: points = [[0,0],[3,0],[9,2]], k = 3 Output: 3 Explanation: Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.
Constraints:
2 <= points.length <= 105points[i].length == 2-108 <= xi, yi <= 1080 <= k <= 2 * 108xi < xj for all 1 <= i < j <= points.lengthxi form a strictly increasing sequence.Problem Overview: You are given points sorted by x. For any pair (i, j) where i < j and xj - xi ≤ k, maximize the equation yi + yj + |xi - xj|. Because the points are sorted, |xi - xj| becomes xj - xi, which lets you rearrange the formula into (yi - xi) + (yj + xj).
Approach 1: Optimized Brute Force with Binary Search (O(n²) worst case, O(1) space)
The constraint xj - xi ≤ k limits which previous points can pair with the current point. For each index j, use binary search to find the earliest index i such that the distance constraint still holds. Then iterate through that valid range and compute the equation value. The binary search reduces the search range compared to naive brute force, but the inner scan can still degrade to O(n), leading to O(n²) time in dense cases. This approach mainly helps you understand the constraint window before introducing more advanced data structures.
Approach 2: Heap-Based Sliding Window (O(n log n) time, O(n) space)
The equation can be rewritten as (yi - xi) + (yj + xj). While iterating through points as j, you only need the maximum value of (yi - xi) among points whose x distance from xj is at most k. Maintain a max heap storing pairs (yi - xi, xi). As you process each point, remove heap elements where xj - xi > k since they fall outside the valid window.
The top of the heap always gives the best candidate for (yi - xi). Combine it with (yj + xj) to update the answer. Then push the current point's (yj - xj) into the heap for future iterations. The heap ensures fast retrieval of the best candidate while the sliding window constraint is enforced dynamically. This approach uses concepts from sliding window and heap (priority queue) problems.
Alternative Optimization: Monotonic Queue (O(n) time, O(n) space)
A stronger optimization replaces the heap with a deque that maintains candidates in decreasing order of (yi - xi). Before adding a new point, remove elements from the front whose x distance exceeds k. Then remove elements from the back if their (yi - xi) value is smaller than the current one. The deque remains monotonic, so the front always holds the best candidate. This eliminates the log n heap operations and achieves linear time using a monotonic queue.
Recommended for interviews: The heap-based sliding window is the most common interview solution because it clearly demonstrates the algebraic transformation and window filtering. Explaining the brute force first shows understanding of the constraint. Implementing the heap or monotonic deque version proves you can optimize to near-linear time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Optimized Brute Force with Binary Search | O(n²) worst case | O(1) | Useful for understanding the distance constraint and validating the formula transformation |
| Heap-Based Sliding Window | O(n log n) | O(n) | General optimal solution using a priority queue to track the best (yi - xi) |
| Monotonic Queue | O(n) | O(n) | Best theoretical performance when you maintain a decreasing deque of candidates |