# Max Value of Equation
**Difficulty:** HARD
[External](https://leetcode.com/problems/max-value-of-equation)
Canonical: https://scaleengineer.com/dsa/problems/max-value-of-equation
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue
---
## Problem
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`.

**Example 1:**

**Input:** points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
**Output:** 4
**Explanation:** The first two points satisfy the condition |xi - xj| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.
No other pairs satisfy the condition, so we return the max of 4 and 1.

**Example 2:**

**Input:** points = [[0,0],[3,0],[9,2]], k = 3
**Output:** 3
**Explanation:** Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.

**Constraints:**

* `2 <= points.length <= 105`
* `points[i].length == 2`
* `-108 <= xi, yi <= 108`
* `0 <= k <= 2 * 108`
* `xi < xj` for all `1 <= i < j <= points.length`
* `xi` form a strictly increasing sequence.

# Approaches
## Brute Force
This approach involves checking every possible pair of points `(i, j)` where `i < j`. For each pair, we verify if it satisfies the condition `|xi - xj| <= k`. If it does, we calculate the equation's value and update our maximum result. This is the most straightforward but least efficient way to solve the problem.
**Time:** O(N^2), where N is the number of points. The two nested loops iterate through approximately N^2/2 pairs, leading to a quadratic time complexity. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** It is very simple to understand and implement.; It requires no extra space, making it memory efficient.
**Cons:** This approach is very slow due to its O(N^2) time complexity and will result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.
### Explanation
The problem asks to maximize `yi + yj + |xi - xj|` given `|xi - xj| <= k` and `i < j`. Since the points are sorted by x-coordinates (`xi < xj` for `i < j`), the condition `|xi - xj| <= k` simplifies to `xj - xi <= k`, and the equation becomes `yi + yj + xj - xi`. The brute-force algorithm systematically iterates through all pairs of indices `(i, j)` with `i < j`. For each pair, it checks if `points[j][0] - points[i][0] <= k`. If the condition holds, it computes `points[i][1] + points[j][1] + points[j][0] - points[i][0]` and compares it with the maximum value found so far. This process is repeated for all pairs to find the global maximum.

```java
class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int maxVal = Integer.MIN_VALUE;
        int n = points.length;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                int xj = points[j][0];
                int yj = points[j][1];
                int xi = points[i][0];
                int yi = points[i][1];
                if (xj - xi <= k) {
                    maxVal = Math.max(maxVal, yi + yj + xj - xi);
                } else {
                    // Since points are sorted by x, if the current i is too far,
                    // any earlier i will also be too far. We could break here,
                    // but the inner loop starts from 0, so this optimization is tricky.
                    // A simple loop from j-1 down to 0 would benefit from this break.
                }
            }
        }
        return maxVal;
    }
}
```
### Algorithm
*   Initialize a variable `maxVal` to the smallest possible integer value.
*   Use a nested loop structure. The outer loop iterates with index `j` from 1 to `n-1`, where `n` is the number of points.
*   The inner loop iterates with index `i` from 0 to `j-1`.
*   For each pair of points `(i, j)`, retrieve their coordinates `(xi, yi)` and `(xj, yj)`.
*   Check if the condition `xj - xi <= k` is satisfied. Since the points are sorted by x-coordinates, `|xi - xj|` is equivalent to `xj - xi`.
*   If the condition holds, calculate the value of the equation: `currentVal = yi + yj + xj - xi`.
*   Update `maxVal` by taking the maximum of `maxVal` and `currentVal`.
*   After both loops complete, `maxVal` will hold the maximum value of the equation for any valid pair of points. Return `maxVal`.

## Using a Max Heap (Priority Queue)
This approach improves upon the brute-force method by optimizing the search for the best point `i` for each point `j`. We can rewrite the equation as `(yj + xj) + (yi - xi)`. For each `j`, we need to find the maximum value of `yi - xi` among all previous points `i` that satisfy `xj - xi <= k`. A max heap can be used to efficiently track the maximum `yi - xi` value in the valid 'window' of points.
**Time:** O(N log N). We iterate through N points. For each point, we perform at most one insertion (`offer`) and some number of removals (`poll`). Each heap operation takes O(log N) time. · **Space:** O(N), as the priority queue can store up to N elements in the worst-case scenario (e.g., when `k` is very large).
**Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to pass the time limits for the given constraints.
**Cons:** While much better than brute force, it is not the most optimal solution as the heap operations lead to a logarithmic factor in the time complexity.; It requires O(N) extra space for the heap.
### Explanation
The core idea is to optimize the search for the best preceding point `i` for each point `j`. By rewriting the equation as `(yj + xj) + (yi - xi)`, we see that for a fixed `j`, we want to maximize `yi - xi` over all `i < j` such that `xi >= xj - k`. A max heap is a suitable data structure for this task. It can store the `yi - xi` values of the points encountered so far and provide the maximum one in logarithmic time. As we iterate through points `j`, we first remove any points from the heap that are now outside the valid window (i.e., `xj - xi > k`). Then, we use the top of the heap (which gives the max `yi - xi` in the current window) to calculate a candidate for the maximum equation value. Finally, we add the current point's `yj - xj` value to the heap for consideration by subsequent points.

```java
import java.util.PriorityQueue;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        // Max heap storing {yi - xi, xi}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int maxVal = Integer.MIN_VALUE;

        for (int[] point : points) {
            int xj = point[0];
            int yj = point[1];

            // Remove points from the heap that are outside the window k
            while (!pq.isEmpty() && xj - pq.peek()[1] > k) {
                pq.poll();
            }

            // If there's a valid point in the heap, calculate the value
            if (!pq.isEmpty()) {
                int[] prevPointInfo = pq.peek();
                maxVal = Math.max(maxVal, xj + yj + prevPointInfo[0]);
            }

            // Add the current point to the heap
            pq.offer(new int[]{yj - xj, xj});
        }
        return maxVal;
    }
}
```
### Algorithm
*   Rearrange the equation to `(yj + xj) + (yi - xi)`.
*   Initialize `maxVal` to the smallest possible integer value.
*   Create a max heap (PriorityQueue in Java) to store pairs of `{yi - xi, xi}`. The heap will be ordered by the `yi - xi` value in descending order.
*   Iterate through the `points` array with index `j`.
*   For each point `j` with coordinates `(xj, yj)`:
    *   Remove points from the top of the heap whose x-coordinate `xi` does not satisfy `xj - xi <= k`. These points are too far to be paired with `j`.
    *   If the heap is not empty after pruning, the top element represents the point `i` with the maximum `yi - xi` value within the valid window. Calculate the potential maximum value `xj + yj + heap.peek()[0]` and update `maxVal`.
    *   Add the current point's information, `{yj - xj, xj}`, to the heap.
*   Return `maxVal` after the loop.

## Optimized Sliding Window with a Deque
This is the most efficient approach, achieving a linear time complexity. It builds on the same observation that for each point `j`, we need to find the maximum `yi - xi` for valid preceding points `i`. Instead of a heap, it uses a double-ended queue (deque) to maintain candidate points `i` in a sliding window. The deque stores indices of points and is cleverly maintained to ensure that the head of the deque always corresponds to the point with the maximum `yi - xi` value within the current valid window.
**Time:** O(N). Each point's index is added to and removed from the deque at most once. The main loop runs N times, and the inner `while` loops have an amortized constant time complexity over the entire execution, leading to a linear time overall. · **Space:** O(N) in the worst case. The deque could hold indices of all points if `k` is large. In practice, the space is O(W) where W is the maximum number of points that can fit in a window of size `k`.
**Pros:** It is the most optimal solution with a linear time complexity.; It efficiently solves the problem well within the time limits for the given constraints.
**Cons:** The logic, particularly for maintaining the deque property, is more complex to grasp compared to the other approaches.
### Explanation
This solution treats the problem as a 'sliding window maximum' problem. The equation `(yj + xj) + (yi - xi)` shows that for each `j`, we need the maximum `yi - xi` from a window of previous points defined by `xj - xi <= k`. A deque is perfect for this. It will store indices of candidate points. We maintain two properties:
1.  The window of points in the deque is always valid for the current `j` (we remove outdated points from the front).
2.  The `yi - xi` values for the indices in the deque are always in decreasing order. This ensures `deque.peekFirst()` gives the maximum `yi - xi`.
To maintain the second property, before adding a new index `j`, we remove all indices from the back whose points have a smaller or equal `yi - xi` value. This is because the new point `j` is a better or equal candidate for all future calculations and is 'closer', making the removed points redundant.

```java
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        // Deque will store indices of points
        Deque<Integer> deque = new ArrayDeque<>();
        int maxVal = Integer.MIN_VALUE;

        for (int j = 0; j < points.length; j++) {
            int xj = points[j][0];
            int yj = points[j][1];

            // 1. Remove points from the front that are outside the window k
            while (!deque.isEmpty() && xj - points[deque.peekFirst()][0] > k) {
                deque.pollFirst();
            }

            // 2. Calculate max value with the best point in the window
            if (!deque.isEmpty()) {
                int i = deque.peekFirst();
                maxVal = Math.max(maxVal, xj + yj + points[i][1] - points[i][0]);
            }

            // 3. Maintain the decreasing property of (y-x) in the deque
            int currentDiff = yj - xj;
            while (!deque.isEmpty() && points[deque.peekLast()][1] - points[deque.peekLast()][0] <= currentDiff) {
                deque.pollLast();
            }
            
            // 4. Add current point's index to the deque
            deque.offerLast(j);
        }
        return maxVal;
    }
}
```
### Algorithm
*   Rearrange the equation to `(yj + xj) + (yi - xi)`.
*   Initialize `maxVal` to the smallest possible integer value.
*   Create a double-ended queue (deque) to store the *indices* of the points.
*   Iterate through the `points` array with index `j`.
*   For each point `j` with coordinates `(xj, yj)`:
    1.  **Prune Front:** Remove indices `i` from the front of the deque if `xj - points[i][0] > k`. These points are now outside the valid window.
    2.  **Calculate Max:** If the deque is not empty, the index `i` at the front (`deque.peekFirst()`) corresponds to the point with the maximum `yi - xi` in the window. Calculate `xj + yj + points[i][1] - points[i][0]` and update `maxVal`.
    3.  **Prune Back:** Remove indices `p` from the back of the deque if `points[p][1] - points[p][0] <= yj - xj`. This maintains a strictly decreasing order of `y-x` values in the deque, ensuring the front is always the maximum.
    4.  **Add Current:** Add the current index `j` to the back of the deque.
*   Return `maxVal` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int findMaxValueOfEquation(int[][] points, int k) {
    int ans = -(1 << 30);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->b[0] - a[0]);
    for (var p : points) {
      int x = p[0], y = p[1];
      while (!pq.isEmpty() && x - pq.peek()[1] > k) {
        pq.poll();
      }
      if (!pq.isEmpty()) {
        ans = Math.max(ans, x + y + pq.peek()[0]);
      }
      pq.offer(new int[]{y - x, x});
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMaxValueOfEquation(vector<vector<int>> &points, int k) {
    int ans = -(1 << 30);
    priority_queue<pair<int, int>> pq;
    for (auto &p : points) {
      int x = p[0], y = p[1];
      while (pq.size() && x - pq.top().second > k) {
        pq.pop();
      }
      if (pq.size()) {
        ans = max(ans, x + y + pq.top().first);
      }
      pq.emplace(y - x, x);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int: ans = - inf pq = [] for x, y in points: while pq and x - pq[0][1] > k: heappop(pq) if pq: ans = max(ans, x + y - pq[0][0]) heappush(pq, (x - y, x)) return ans

```