Leetcode 1499. Max Value of Equation
Problem Explanation
The problem is asking us to find two points i
and j
in the given array of points on a plane, where the sum of yi + yj + |xi - xj|
is the maximum. There is a key constraint, that the difference between xi
and xj
should be less than or equal to a specific value k
provided in the problem's input. The points are already sorted by xi
, gradually increasing in value.
Walkthrough Example
Let's take an example where points are [[1,3],[2,0],[5,10],[6,-10]]
and value of k
is 1
.
In this case, the difference |xi - xj|
is equal or less than 1 for :
- First and second points - The sum
yi + yj + |xi - xj|
for these is3 + 0 + |1 - 2| = 4
. - Third and fourth points - The sum
yi + yj + |xi - xj|
for these is10 + (-10) + |5 - 6| = 1
.
The maximum between these sums is 4
. Hence, the output will be 4
.
Solution Approach
We iterate through each point in the plane and put it in a max heap. We select pairs of points where |xi - xj| <= k
and calculate the maximum value for yi + yj + |xi - xj|
. We maintain the max heap in a way that it always contains the maximum value of yi - xi
.
Each point is added and removed at most once from the heap. The heap is implemented in such a way that both addition and removal of elements take logarithmic time.
Python solution
1 2python 3import heapq 4 5class Solution: 6 def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int: 7 ans = float("-inf") 8 heap = [] 9 10 for x, y in points: 11 while heap and heap[0][1] < x - k: # remove points that don't satisfy |xi - xj| condition 12 heapq.heappop(heap) 13 if heap: 14 ans = max(ans, heap[0][0] + y + x) # calculate max value of yi + yj + |xi - xj| 15 heapq.heappush(heap, [y - x, x]) # insert new point into the heap 16 return ans
Java solution
1
2java
3class Solution {
4 public int findMaxValueOfEquation(int[][] points, int k) {
5 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
6 int res = Integer.MIN_VALUE;
7 for (int[] point : points) {
8 while (!pq.isEmpty() && point[0] - pq.peek()[1] > k) {
9 pq.poll();
10 }
11 if (!pq.isEmpty()) {
12 res = Math.max(res, point[0] + point[1] + pq.peek()[0]);
13 }
14 pq.offer(new int[]{point[1] - point[0], point[0]});
15 }
16 return res;
17 }
18}
JavaScript solution
1 2javascript 3var findMaxValueOfEquation = function(points, k) { 4 let res = -Infinity; 5 let heap = []; // javascript has no inbuilt Priority Queue, we are using an array as a MaxHeap 6 for(let p of points) { 7 while(heap.length && p[0] - heap[0][1] > k) { 8 heap.shift(); // remove front of the array 9 } 10 if(heap.length) { 11 res = Math.max(res, heap[0][0] + p[0] + p[1]); 12 } 13 while(heap.length && heap[heap.length - 1][0] <= p[1] - p[0]) { 14 heap.pop(); // remove from the end of the array 15 } 16 heap.push([p[1] - p[0], p[0]]); 17 } 18 return res; 19};
C++ solution
1
2c++
3class Solution {
4public:
5 int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
6 int ans = INT_MIN;
7 priority_queue<pair<int, int>> maxHeap; // (y - x, x)
8
9 for (const vector<int>& p : points) {
10 const int x = p[0];
11 const int y = p[1];
12 while (!maxHeap.empty() && x - maxHeap.top().second > k)
13 maxHeap.pop();
14 if (!maxHeap.empty())
15 ans = max(ans, x + y + maxHeap.top().first);
16 maxHeap.emplace(y - x, x);
17 }
18
19 return ans;
20 }
21};
C# solution
1 2csharp 3public class Solution { 4 public int FindMaxValueOfEquation(int[][] points, int k) { 5 int res = Int32.MinValue; 6 var heap = new SortedSet<(int, int)>((a,b) => a.Item1 == b.Item1 ? a.Item2.CompareTo(b.Item2) : b.Item1.CompareTo(a.Item1)); 7 foreach (var point in points) { 8 while (heap.Count > 0 && point[0] - heap.First().Item2 > k) heap.Remove(heap.First()); 9 if (heap.Count > 0) res = Math.Max(res, point[0] + point[1] + heap.First().Item1); 10 heap.Add((point[1] - point[0], point[0])); 11 } 12 return res; 13 } 14}
Overall Explanation
The key is to realize which observations can help us solve the problem efficiently:
- Maximum value of
yi + yj + |xi - xj|
is equivalent to finding maximum values ofyj + xj + (yi - xi)
. This helps us in breaking down the problem into simpler terms where we are effectively finding the maximum value ofyi - xi
while iterating through the points. - As the points are already sorted in increasing order of
xi
, we can intelligently select which points we need to consider for each 'j'. We only need to consider points wherexi - xj <= k
, which essentially means we have to consider points on the left of 'j' which are not more than 'k' units away.
By making these observations, we can leverage the heap data structure (PriorityQueue in some languages) and keep track of points offering the maximum value of yi - xi
as we iterate through the points. For each point, we add xj + yj
to the current max value and continue updating our result if we find a greater sum. The heap ensures a time complexity of O(n*log(n)) for this problem.
Pseudocode
Here's a high-level pseudocode of the solution:
- Initialize max_heap and ans to hold the maximum values of
yi - xi
and the final answer respectively. - Iterate through points. For each point do:
- Discard points from the max_heap where
xi - xj > k
. - Update the ans with
max(ans, xj + yj + max_value_in_heap)
. - Add
yi - xi
to max heap.
- Discard points from the max_heap where
- Answer is stored in ans.
Additional Notes
Heap structures are chosen for this problem due to their property of maintaining order based on a specific comparator. In our case, this comparator is the value of yi - xi
. Python and C++ have inbuilt support for max heaps while Java utilizes PriorityQueue, and JavaScript and C# require custom implementations.
While this solution works excellently for this problem. Remember, finding the right data structure or construct (like max heap, in this case) often comes down to understanding the problem statement and making key observations about the constraints and requirements of the problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.