#1499 - Max Value of Equation

Hard • View on LeetCode • View on GitHub

Array Heap Priority Queue Sliding Window Queue Monotonic Queue

Problem Description

You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [xi, yi] such that xi < xj for all 1 <= i < j <= points.length. You are also given an integer k.

Return the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length.

It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi - xj| <= k.

Solution

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number}
 */
var findMaxValueOfEquation = function(points, k) {
  let result = -Infinity;
  const q = [];

  for (let j = 0; j < points.length; j++) {
    const [xj, yj] = points[j];

    while (q.length && xj - points[q[0]][0] > k) {
      q.shift();
    }

    if (q.length) {
      const [xi, yi] = points[q[0]];
      result = Math.max(result, yi + yj + xj - xi);
    }

    while (q.length && yj - xj >= points[q[q.length - 1]][1] - points[q[q.length - 1]][0]) {
      q.pop();
    }

    q.push(j);
  }

  return result;
};