Max Value of Equation

hard monotonic deque sliding window

Problem

You get an array of 2-D points, points[i] = [xi, yi], sorted by strictly increasing x-coordinate, and an integer k. Over all pairs i < j with |xi − xj| ≤ k, return the maximum value of yi + yj + |xi − xj|. At least one valid pair is guaranteed.

Since the x's are sorted, for i < j the value equals (xj + yj) + (yi − xi). So while scanning, each new point only needs the largest yi − xi among earlier points within x-distance k — a sliding-window maximum, maintained by a monotonic decreasing deque.

Inputpoints = [[1,3],[2,0],[5,10],[6,-10]], k = 1

Output4

Pair (1,3) with (2,0): 3 + 0 + |1 − 2| = 4. The only other in-range pair, (5,10) with (6,−10), gives just 10 − 10 + 1 = 1.

points (x:y, comma-separated, x strictly increasing)

def find_max_value_of_equation(points, k):
    dq = deque()                  # (x, y - x), front keeps the max
    best = float('-inf')
    for x, y in points:
        while dq and x - dq[0][0] > k:
            dq.popleft()          # window: too far left, expire
        if dq:
            best = max(best, x + y + dq[0][1])
        while dq and dq[-1][1] <= y - x:
            dq.pop()              # dominated by the new point
        dq.append((x, y - x))
    return best

function findMaxValueOfEquation(points, k) {
  const dq = [];                       // [x, y - x], front keeps the max
  let best = -Infinity;
  for (const [x, y] of points) {
    while (dq.length && x - dq[0][0] > k) {
      dq.shift();                      // window: too far left, expire
    }
    if (dq.length) {
      best = Math.max(best, x + y + dq[0][1]);
    }
    while (dq.length && dq[dq.length - 1][1] <= y - x) {
      dq.pop();                        // dominated by the new point
    }
    dq.push([x, y - x]);
  }
  return best;
}

public int findMaxValueOfEquation(int[][] points, int k) {
    Deque<int[]> dq = new ArrayDeque<>();  // {x, y - x}, front keeps the max
    int best = Integer.MIN_VALUE;
    for (int[] p : points) {
        int x = p[0], y = p[1];
        while (!dq.isEmpty() && x - dq.peekFirst()[0] > k) {
            dq.pollFirst();                 // window: too far left, expire
        }
        if (!dq.isEmpty()) {
            best = Math.max(best, x + y + dq.peekFirst()[1]);
        }
        while (!dq.isEmpty() && dq.peekLast()[1] <= y - x) {
            dq.pollLast();                  // dominated by the new point
        }
        dq.offerLast(new int[]{x, y - x});
    }
    return best;
}

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    deque<pair<int,int>> dq;                // {x, y - x}, front keeps the max
    int best = INT_MIN;
    for (auto& p : points) {
        int x = p[0], y = p[1];
        while (!dq.empty() && x - dq.front().first > k) {
            dq.pop_front();                 // window: too far left, expire
        }
        if (!dq.empty()) {
            best = max(best, x + y + dq.front().second);
        }
        while (!dq.empty() && dq.back().second <= y - x) {
            dq.pop_back();                  // dominated by the new point
        }
        dq.push_back({x, y - x});
    }
    return best;
}

Explanation

The trick is an algebraic rewrite. The points come sorted by x, so for any pair i < j we have |xi − xj| = xj − xi, and the target becomes yi + yj + xj − xi = (xj + yj) + (yi − xi). Scanning left to right, point j contributes a fixed xj + yj; all it needs is the largest yi − xi among earlier points satisfying xj − xi ≤ k. That is exactly a sliding-window maximum.

A monotonic deque maintains that window maximum in amortized O(1). Each visited point is stored as the pair (y − x, x), and the deque keeps its y − x values in decreasing order from front to back, so the front is always the best available partner. Before pairing, we expire from the front every entry with x < xj − k — those points are too far left and can never re-enter the window.

After taking the candidate x + y + front, we pop from the back every entry whose y − x is ≤ the new point's. Such an entry is dominated: it is both weaker and further left (so it expires sooner), meaning it can never be the best partner again. Then the new point is pushed at the back, preserving the decreasing order.

Walking the default example with k = 1: after pushing (1,3) as (y−x=2, x=1), point (2,0) finds the front within range and scores 2 + 0 + 2 = 4. Point (5,10) expires both stored points (x-gaps 4 and 3 exceed k), so it gets no partner and the deque restarts with (5, x=5). Point (6,−10) pairs with that front for 6 − 10 + 5 = 1, which does not beat 4. The answer is 4.

Every point is pushed once and popped at most once — from the front (expiry) or the back (domination) — so the whole scan does O(n) deque operations. Time is O(n) and the deque holds at most n entries, giving O(n) space.

Time: O(n) Space: O(n)