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.
This approach utilizes a max-heap to keep track of the maximum value of yi - xi for valid indices i, where valid means i is within the window of xj - xi <= k. This helps efficiently compute the possible maximum value of the equation yj + xj + (yi - xi).
In C, we use a simple array to represent our points and a dual-pointer strategy to simulate the sliding window effect. By iterating over the sorted array with two pointers, we ensure each point is considered within a defined window size & k. Whenever window restrictions are violated, we adjust the left pointer. This ensures our resultant equation meets the condition xj - xi <= k, maximizing the value.
Time Complexity: O(n), where n is the number of points. We essentially scan through the points with the right pointer and adjust the left pointer as needed.
Space Complexity: O(1), as we are using constant space.
This approach uses binary search in combination with brute force to determine valid pairs by leveraging the sorted x-values, to effectively limit the search space for y-values which complement them. This approach isn't for optimal performance but demonstrates a valid attempt at improving a straightforward n^2 approach.
This refined brute force approach makes use of a nested loop. By exploiting the sorted x-coordinates, it employs the immediate current loop index to avoid unnecessary calculations past the point where x-compliance is violated. This sparks efficiency beyond basic brute force.
Time Complexity: O(n²), since each element is checked against subsequent ones up to x constraint.
Space Complexity: O(1), as no additional data structure is utilized.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Heap-Based Sliding Window | Time Complexity: O(n), where n is the number of points. We essentially scan through the points with the right pointer and adjust the left pointer as needed. |
| Optimized Brute Force with Binary Search | Time Complexity: O(n²), since each element is checked against subsequent ones up to x constraint. |
| Default Approach | — |
| 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 |
Leetcode 1499. Max Value of Equation • Fraz • 14,380 views views
Watch 8 more video solutions →Practice Max Value of Equation with our built-in code editor and test cases.
Practice on FleetCode