Max Value of Equation Hard 0 attempts
LeetCode ↗

Max Value of Equation

Hard ArrayTwo Pointers LeetCode

You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, and an integer k. Return the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length.

Sample Input
points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
Sample Output
4
Constraints
  • 2 <= points.length <= 10^5
  • points is sorted by xi
  • 1 <= k <= 2 * 10^8
Test Cases
Case 1
Args: [[[1,3],[2,0],[5,10],[6,-10]],1] Expected: 4
Topics
ArrayTwo Pointers

Maximize (yi + yj) + |xi - xj|. Since points are sorted by x, this simplifies to maximizing (yj + xj) + (yi - xi) where j > i. Use a deque to maintain the maximum yi - xi for points within x-distance k.

function findMaxValueOfEquation(points, k) {
  const deque = [];
  let result = -Infinity;

  for (const [xj, yj] of points) {
    while (deque.length && xj - deque[0][1] > k) {
      deque.shift();
    }

    if (deque.length) {
      result = Math.max(result, yj + xj + deque[0][0]);
    }

    const val = yj - xj;
    while (deque.length && deque[deque.length - 1][0] <= val) {
      deque.pop();
    }
    deque.push([val, xj]);
  }

  return result;
}

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

Saved in this browser only. Private to you.

JavaScript