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 :

1. First and second points - The sum yi + yj + |xi - xj| for these is 3 + 0 + |1 - 2| = 4.
2. Third and fourth points - The sum yi + yj + |xi - xj| for these is 10 + (-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:

1. Maximum value of yi + yj + |xi - xj| is equivalent to finding maximum values of yj + xj + (yi - xi). This helps us in breaking down the problem into simpler terms where we are effectively finding the maximum value of yi - xi while iterating through the points.
2. 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 where xi - 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:

1. Initialize max_heap and ans to hold the maximum values of yi - xi and the final answer respectively.
2. 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.
3. 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.