Max Value of Equation

Max Value of Equation

What is this problem about?

The Max Value of Equation problem provides an array of points [x, y] sorted by their x values, and an integer k. You need to find the maximum value of the equation y_i + y_j + |x_i - x_j| for any pair of distinct points where |x_i - x_j| <= k. Since the array is sorted by x and $x_i < x_j$, the absolute value can be simplified, transforming the equation into (y_i - x_i) + (y_j + x_j).

Why is this asked in interviews?

This is a Hard-level problem that perfectly bridges algebra and data structure optimization. Interviewers ask it because it forces candidates to perform algebraic manipulation to decouple variables. Once decoupled, the problem cleanly transforms into a classic Sliding Window optimization using a Priority Queue or a Monotonic Deque.

Algorithmic pattern used

This problem relies on Algebraic Decoupling and a Monotonic Queue (or Max Heap).

1. Rewrite the equation: y_i + y_j + (x_j - x_i) equals (y_j + x_j) + (y_i - x_i).
2. As we iterate through the points, treating the current point as j, (y_j + x_j) is a fixed constant. To maximize the whole equation, we simply need to find a previous point i that maximizes (y_i - x_i), subject to the constraint x_j - x_i <= k.
3. We maintain a Monotonic Decreasing Deque that stores pairs [y_i - x_i, x_i]. The front of the queue will always hold the maximum y_i - x_i seen so far. We pop from the front if the constraint k is violated, calculate our max, and then push the current point's data to the back, maintaining monotonic order.

Example explanation

Points: [[1,3], [2,0], [5,10]], k = 1.

• j = 0: Point [1, 3]. y_i - x_i = 3 - 1 = 2. Push [2, 1] to Deque. Max = -infinity.
• j = 1: Point [2, 0].
  • Check constraint: x_j (2) - front.x (1) = 1 <= 1. Valid!
  • Calculate equation: (y_j + x_j) is 0 + 2 = 2. front.val is 2. Sum = $2 + 2 = 4$. Max = 4.
  • Current point's y_i - x_i = 0 - 2 = -2. Push [-2, 2]. Deque: [[2, 1], [-2, 2]].
• j = 2: Point [5, 10].
  • Check constraint: x_j (5) - front.x (1) = 4 > 1. Invalid! Pop front.
  • Check constraint: x_j (5) - new front.x (2) = 3 > 1. Invalid! Pop front. Deque is empty.
  • Cannot form a pair. Push [5, 5]. The maximum value found is 4.

Common mistakes candidates make

The most frequent mistake is trying to evaluate the original equation y_i + y_j + |x_i - x_j| directly using nested loops. This results in $O(N^2)$ time and a Time Limit Exceeded error. Failing to realize that the absolute value can be cleanly dropped (because the array is sorted, $x_j$ is always $\ge x_i$) prevents candidates from separating the i terms from the j terms.

Interview preparation tip

When you see an equation involving two indices in an array problem, immediately try to group the terms by index. Turn f(i, j) into g(i) + h(j). Once you isolate the i terms into a single block, you can use a sliding window data structure (like a Max Heap or Deque) to track the absolute best historical value of g(i) in $O(1)$ amortized time.