Problem Description

You are given an array points where each element is a pair [x, y] representing a point on a 2D plane, sorted in increasing order of x. You are also given an integer k. Your task is to find the maximum value of the equation:

yi + yj + |xi - xj|

where |xi - xj| <= k and i < j (i.e., xi < xj because the array is sorted).

• Each pair of points can only be used once in the calculation.
• The difference in x values between the two points must not exceed k.
• There is guaranteed to be at least one valid pair that satisfies these constraints.

Thought Process

At first glance, the problem asks us to consider all pairs of points and compute the equation for each, which would be a classic brute-force approach. However, with the constraint that points is sorted by x, and that we must keep |xi - xj| <= k with i < j, we can optimize.

The brute-force approach would involve checking every possible pair, but this is inefficient for large inputs. We need to find a way to efficiently find, for each j, the best i such that xj - xi <= k and the value of the equation is maximized.

By rearranging the equation, we can see an opportunity for optimization. Since the array is sorted, we can use a data structure to keep track of the best candidates for i as we iterate over j.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Equation Rearrangement:
   • The equation yi + yj + |xi - xj| simplifies to yi + yj + xj - xi (since xj > xi).
   • Rearranged: (yi - xi) + (yj + xj).
   • For each j, we want to find the maximum yi - xi among all i where xj - xi <= k.
2. Efficient Tracking with Deque:
   • As we iterate through the points, we can use a double-ended queue (deque) to keep track of candidates for i.
   • The deque will store pairs of (xi, yi - xi), always maintaining the largest yi - xi at the front.
   • When considering point j, we remove from the deque any points where xj - xi > k, as they are no longer valid.
   • The front of the deque represents the best candidate for i for the current j.
3. Iterative Update:
   • For each j, compute the candidate value using the front of the deque, and update the answer if it's better.
   • Then, add the current (xj, yj - xj) to the deque, maintaining the monotonicity (remove from the back any values less than or equal to the new one).
4. Final Output:
   • After processing all points, return the maximum value found.

This approach ensures that each point is added and removed from the deque at most once, resulting in an efficient solution.

Example Walkthrough

Let's consider the input: points = [[1,3],[2,0],[3,10],[4,5],[5,3]] and k = 1.

1. Start with an empty deque and max_value = -inf.
2. For j = 0 (x=1, y=3): No previous points, just add (1, 2) (y-x) to deque.
3. For j = 1 (x=2, y=0):
   • Check deque: 2-1=1 <= 1, valid.
   • Candidate value: 0+2 + (3-1) = 0+2+2=4, but actually using rearranged: (3-1)+(0+2)=2+2=4.
   • Update max_value = 4.
   • Add (2, -2) to deque.
4. For j = 2 (x=3, y=10):
   • Remove from deque any where 3-1>1 (no, 2 is valid).
   • Candidate: Use front (1,2): 10+3 + (3-1) = 13+2=15 or rearranged: (3-1)+(10+3)=2+13=15.
   • Update max_value = 15.
   • Add (3,7) to deque, remove from back any less than 7.
5. Continue similarly for the rest.

At each step, the deque efficiently maintains the best candidate for maximizing the equation under the constraints.

Time and Space Complexity

• Brute-force approach: O(n²) time, as it checks every pair of points.
• Optimized approach: O(n) time and O(n) space.
  • Each point is added and removed from the deque at most once.
  • We only store at most n points in the deque, so space is O(n).

The use of a deque allows us to efficiently maintain and update the set of candidate points, avoiding unnecessary comparisons.

Summary

The key insight is to rearrange the equation to isolate a term that can be efficiently tracked as we process the points in order. By using a monotonic deque, we maintain the best candidates for maximizing the equation, ensuring that we only consider valid pairs efficiently. This approach takes advantage of the sorted input and the mathematical structure of the equation, resulting in an elegant and optimal solution.

Code Implementation

from collections import deque

class Solution:
    def findMaxValueOfEquation(self, points, k):
        dq = deque()  # stores (x, y-x)
        max_value = float('-inf')
        for x, y in points:
            # Remove points out of window
            while dq and x - dq[0][0] > k:
                dq.popleft()
            # Update answer if possible
            if dq:
                max_value = max(max_value, y + x + dq[0][1])
            # Maintain deque in decreasing order of (y-x)
            while dq and dq[-1][1] <= y - x:
                dq.pop()
            dq.append((x, y - x))
        return max_value
      

#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<pair<int, int>> dq; // (x, y-x)
        int maxValue = INT_MIN;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            while (!dq.empty() && x - dq.front().first > k) {
                dq.pop_front();
            }
            if (!dq.empty()) {
                maxValue = max(maxValue, y + x + dq.front().second);
            }
            while (!dq.empty() && dq.back().second <= y - x) {
                dq.pop_back();
            }
            dq.emplace_back(x, y - x);
        }
        return maxValue;
    }
};
      

import java.util.*;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        Deque<int[]> dq = new ArrayDeque<>(); // [x, y-x]
        int maxValue = Integer.MIN_VALUE;
        for (int[] p : points) {
            int x = p[0], y = p[1];
            while (!dq.isEmpty() && x - dq.peekFirst()[0] > k) {
                dq.pollFirst();
            }
            if (!dq.isEmpty()) {
                maxValue = Math.max(maxValue, y + x + dq.peekFirst()[1]);
            }
            while (!dq.isEmpty() && dq.peekLast()[1] <= y - x) {
                dq.pollLast();
            }
            dq.addLast(new int[]{x, y - x});
        }
        return maxValue;
    }
}
      

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number}
 */
var findMaxValueOfEquation = function(points, k) {
    let dq = []; // stores [x, y-x]
    let maxValue = -Infinity;
    for (const [x, y] of points) {
        while (dq.length > 0 && x - dq[0][0] > k) {
            dq.shift();
        }
        if (dq.length > 0) {
            maxValue = Math.max(maxValue, y + x + dq[0][1]);
        }
        while (dq.length > 0 && dq[dq.length - 1][1] <= y - x) {
            dq.pop();
        }
        dq.push([x, y - x]);
    }
    return maxValue;
};