Max Value of Equation
HardPrompt
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 < xjfor all1 <= i < j <= points.lengthxiform a strictly increasing sequence.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of points (i, j) where i < j. For each pair, we verify if it satisfies the condition |xi - xj| <= k. If it does, we calculate the equation's value and update our maximum result. This is the most straightforward but least efficient way to solve the problem.
Algorithm
- Initialize a variable
maxValto the smallest possible integer value. - Use a nested loop structure. The outer loop iterates with index
jfrom 1 ton-1, wherenis the number of points. - The inner loop iterates with index
ifrom 0 toj-1. - For each pair of points
(i, j), retrieve their coordinates(xi, yi)and(xj, yj). - Check if the condition
xj - xi <= kis satisfied. Since the points are sorted by x-coordinates,|xi - xj|is equivalent toxj - xi. - If the condition holds, calculate the value of the equation:
currentVal = yi + yj + xj - xi. - Update
maxValby taking the maximum ofmaxValandcurrentVal. - After both loops complete,
maxValwill hold the maximum value of the equation for any valid pair of points. ReturnmaxVal.
Walkthrough
The problem asks to maximize yi + yj + |xi - xj| given |xi - xj| <= k and i < j. Since the points are sorted by x-coordinates (xi < xj for i < j), the condition |xi - xj| <= k simplifies to xj - xi <= k, and the equation becomes yi + yj + xj - xi. The brute-force algorithm systematically iterates through all pairs of indices (i, j) with i < j. For each pair, it checks if points[j][0] - points[i][0] <= k. If the condition holds, it computes points[i][1] + points[j][1] + points[j][0] - points[i][0] and compares it with the maximum value found so far. This process is repeated for all pairs to find the global maximum.
class Solution { public int findMaxValueOfEquation(int[][] points, int k) { int maxVal = Integer.MIN_VALUE; int n = points.length; for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { int xj = points[j][0]; int yj = points[j][1]; int xi = points[i][0]; int yi = points[i][1]; if (xj - xi <= k) { maxVal = Math.max(maxVal, yi + yj + xj - xi); } else { // Since points are sorted by x, if the current i is too far, // any earlier i will also be too far. We could break here, // but the inner loop starts from 0, so this optimization is tricky. // A simple loop from j-1 down to 0 would benefit from this break. } } } return maxVal; }}Complexity
Time
O(N^2), where N is the number of points. The two nested loops iterate through approximately N^2/2 pairs, leading to a quadratic time complexity.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
It is very simple to understand and implement.
It requires no extra space, making it memory efficient.
Cons
This approach is very slow due to its O(N^2) time complexity and will result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.
This approach improves upon the brute-force method by optimizing the search for the best point i for each point j. We can rewrite the equation as (yj + xj) + (yi - xi). For each j, we need to find the maximum value of yi - xi among all previous points i that satisfy xj - xi <= k. A max heap can be used to efficiently track the maximum yi - xi value in the valid 'window' of points.
Algorithm
- Rearrange the equation to
(yj + xj) + (yi - xi). - Initialize
maxValto the smallest possible integer value. - Create a max heap (PriorityQueue in Java) to store pairs of
{yi - xi, xi}. The heap will be ordered by theyi - xivalue in descending order. - Iterate through the
pointsarray with indexj. - For each point
jwith coordinates(xj, yj):- Remove points from the top of the heap whose x-coordinate
xidoes not satisfyxj - xi <= k. These points are too far to be paired withj. - If the heap is not empty after pruning, the top element represents the point
iwith the maximumyi - xivalue within the valid window. Calculate the potential maximum valuexj + yj + heap.peek()[0]and updatemaxVal. - Add the current point's information,
{yj - xj, xj}, to the heap.
- Remove points from the top of the heap whose x-coordinate
- Return
maxValafter the loop.
Walkthrough
The core idea is to optimize the search for the best preceding point i for each point j. By rewriting the equation as (yj + xj) + (yi - xi), we see that for a fixed j, we want to maximize yi - xi over all i < j such that xi >= xj - k. A max heap is a suitable data structure for this task. It can store the yi - xi values of the points encountered so far and provide the maximum one in logarithmic time. As we iterate through points j, we first remove any points from the heap that are now outside the valid window (i.e., xj - xi > k). Then, we use the top of the heap (which gives the max yi - xi in the current window) to calculate a candidate for the maximum equation value. Finally, we add the current point's yj - xj value to the heap for consideration by subsequent points.
import java.util.PriorityQueue; class Solution { public int findMaxValueOfEquation(int[][] points, int k) { // Max heap storing {yi - xi, xi} PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]); int maxVal = Integer.MIN_VALUE; for (int[] point : points) { int xj = point[0]; int yj = point[1]; // Remove points from the heap that are outside the window k while (!pq.isEmpty() && xj - pq.peek()[1] > k) { pq.poll(); } // If there's a valid point in the heap, calculate the value if (!pq.isEmpty()) { int[] prevPointInfo = pq.peek(); maxVal = Math.max(maxVal, xj + yj + prevPointInfo[0]); } // Add the current point to the heap pq.offer(new int[]{yj - xj, xj}); } return maxVal; }}Complexity
Time
O(N log N). We iterate through N points. For each point, we perform at most one insertion (`offer`) and some number of removals (`poll`). Each heap operation takes O(log N) time.
Space
O(N), as the priority queue can store up to N elements in the worst-case scenario (e.g., when `k` is very large).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Guaranteed to pass the time limits for the given constraints.
Cons
While much better than brute force, it is not the most optimal solution as the heap operations lead to a logarithmic factor in the time complexity.
It requires O(N) extra space for the heap.
This is the most efficient approach, achieving a linear time complexity. It builds on the same observation that for each point j, we need to find the maximum yi - xi for valid preceding points i. Instead of a heap, it uses a double-ended queue (deque) to maintain candidate points i in a sliding window. The deque stores indices of points and is cleverly maintained to ensure that the head of the deque always corresponds to the point with the maximum yi - xi value within the current valid window.
Algorithm
- Rearrange the equation to
(yj + xj) + (yi - xi). - Initialize
maxValto the smallest possible integer value. - Create a double-ended queue (deque) to store the indices of the points.
- Iterate through the
pointsarray with indexj. - For each point
jwith coordinates(xj, yj):- Prune Front: Remove indices
ifrom the front of the deque ifxj - points[i][0] > k. These points are now outside the valid window. - Calculate Max: If the deque is not empty, the index
iat the front (deque.peekFirst()) corresponds to the point with the maximumyi - xiin the window. Calculatexj + yj + points[i][1] - points[i][0]and updatemaxVal. - Prune Back: Remove indices
pfrom the back of the deque ifpoints[p][1] - points[p][0] <= yj - xj. This maintains a strictly decreasing order ofy-xvalues in the deque, ensuring the front is always the maximum. - Add Current: Add the current index
jto the back of the deque.
- Prune Front: Remove indices
- Return
maxValafter the loop.
Walkthrough
This solution treats the problem as a 'sliding window maximum' problem. The equation (yj + xj) + (yi - xi) shows that for each j, we need the maximum yi - xi from a window of previous points defined by xj - xi <= k. A deque is perfect for this. It will store indices of candidate points. We maintain two properties:
- The window of points in the deque is always valid for the current
j(we remove outdated points from the front). - The
yi - xivalues for the indices in the deque are always in decreasing order. This ensuresdeque.peekFirst()gives the maximumyi - xi. To maintain the second property, before adding a new indexj, we remove all indices from the back whose points have a smaller or equalyi - xivalue. This is because the new pointjis a better or equal candidate for all future calculations and is 'closer', making the removed points redundant.
import java.util.Deque;import java.util.ArrayDeque; class Solution { public int findMaxValueOfEquation(int[][] points, int k) { // Deque will store indices of points Deque<Integer> deque = new ArrayDeque<>(); int maxVal = Integer.MIN_VALUE; for (int j = 0; j < points.length; j++) { int xj = points[j][0]; int yj = points[j][1]; // 1. Remove points from the front that are outside the window k while (!deque.isEmpty() && xj - points[deque.peekFirst()][0] > k) { deque.pollFirst(); } // 2. Calculate max value with the best point in the window if (!deque.isEmpty()) { int i = deque.peekFirst(); maxVal = Math.max(maxVal, xj + yj + points[i][1] - points[i][0]); } // 3. Maintain the decreasing property of (y-x) in the deque int currentDiff = yj - xj; while (!deque.isEmpty() && points[deque.peekLast()][1] - points[deque.peekLast()][0] <= currentDiff) { deque.pollLast(); } // 4. Add current point's index to the deque deque.offerLast(j); } return maxVal; }}Complexity
Time
O(N). Each point's index is added to and removed from the deque at most once. The main loop runs N times, and the inner `while` loops have an amortized constant time complexity over the entire execution, leading to a linear time overall.
Space
O(N) in the worst case. The deque could hold indices of all points if `k` is large. In practice, the space is O(W) where W is the maximum number of points that can fit in a window of size `k`.
Trade-offs
Pros
It is the most optimal solution with a linear time complexity.
It efficiently solves the problem well within the time limits for the given constraints.
Cons
The logic, particularly for maintaining the deque property, is more complex to grasp compared to the other approaches.
Solutions
Solution
class Solution {public int findMaxValueOfEquation(int[][] points, int k) { int ans = -(1 << 30); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->b[0] - a[0]); for (var p : points) { int x = p[0], y = p[1]; while (!pq.isEmpty() && x - pq.peek()[1] > k) { pq.poll(); } if (!pq.isEmpty()) { ans = Math.max(ans, x + y + pq.peek()[0]); } pq.offer(new int[]{y - x, x}); } return ans; }}class Solution {public: int findMaxValueOfEquation(vector<vector<int>> &points, int k) { int ans = -(1 << 30); priority_queue<pair<int, int>> pq; for (auto &p : points) { int x = p[0], y = p[1]; while (pq.size() && x - pq.top().second > k) { pq.pop(); } if (pq.size()) { ans = max(ans, x + y + pq.top().first); } pq.emplace(y - x, x); } return ans; }};class Solution: def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int: ans = - inf pq = [] for x, y in points: while pq and x - pq[0][1] > k: heappop(pq) if pq: ans = max(ans, x + y - pq[0][0]) heappush(pq, (x - y, x)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.