Max Value of Equation Hard 0 attempts
LeetCode ↗

Max Value of Equation

Hard ArrayTwo Pointers LeetCode

You're given an array points of 2D coordinates, already sorted by their x-values, plus an integer k. Among all index pairs i < j whose x-values satisfy |xi - xj| <= k, find the largest possible result of the expression yi + yj + |xi - xj|.

Input Format
Implement findMaxValueOfEquation(points, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
points = [[1,3],[2,0],[5,10],[6,-10]]
k = 1
Output
4

Example 2

Input
points = [[0,0],[3,0],[4,10]]
k = 1
Output
11
Constraints
  • 2 <= points.length <= 10^5
  • -10^8 <= xi, yi <= 10^8
  • x coordinates are strictly increasing.
  • 1 <= k <= 2 * 10^8
  • At least one pair satisfies the distance condition.
Test Cases (2)
Case 1
Args: [[[1,3],[2,0],[5,10],[6,-10]],1] Expected: 4
Case 2
Args: [[[0,0],[3,0],[4,10]],1] Expected: 11
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.

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

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

    if (deque.length > head) {
      result = Math.max(result, yj + xj + deque[head][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