Max Value of Equation

HardSliding Windowsliding window

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given points, where points[i] = [x_i, y_i], sorted by x in **strictly increasing** order, and an integer k. Choose two indices i < j with x_j - x_i <= k and maximize the value y_i + y_j + |x_i - x_j|. Return that maximum value. The input guarantees that at least one valid pair exists. An O(n^2) scan over all pairs is too slow for the largest inputs; aim for O(n).

Examples

Input: points = [[0,2],[3,5],[4,1],[9,4]], k = 4
Output: 10
Pairs within distance 4: `(0,3)` gives 2+5+3 = 10, `(0,4)` gives 7, `(3,4)` gives 7. Point x=9 is too far from all others.
Input: points = [[1,-5],[10,-2],[12,-3]], k = 5
Output: -3
Only `x=10` and `x=12` are close enough: -2 + -3 + 2 = -3.

Constraints

  • `2 <= points.length <= 10^5`
  • `-10^8 <= x_i, y_i <= 10^8`
  • `0 <= k <= 2 * 10^8`
  • `x_i < x_{i+1}`
  • At least one pair satisfies `x_j - x_i <= k`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More sliding window problems