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 equationyi + 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.

Examples

Example 1

1
2
3
4

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

1
2
3

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 <= 10^5
  • points[i].length == 2
  • -108 <= xi, yi <= 10^8
  • 0 <= k <= 2 * 10^8
  • xi < xj for all 1 <= i < j <= points.length
  • xi form a strictly increasing sequence.

Solution

Method 1 – Monotonic Queue (Deque) for Sliding Window Maximum

Intuition

The equation can be rewritten as (yi + xi) + (yj - xj) for i < j and |xi - xj| <= k. Since the points are sorted by xi, we can use a deque to maintain the maximum value of yi - xi for all valid i within the window of |xi - xj| <= k as we iterate through j.

Approach

  1. Initialize a deque to store pairs (yi - xi, xi) for candidate points.
  2. Iterate through each point (xj, yj):
    • Remove points from the front of the deque if xj - xi > k (out of window).
    • If the deque is not empty, update the answer with yj + xj + deque[0][0].
    • Maintain the deque in decreasing order of yi - xi by removing from the back.
    • Add (yj - xj, xj) to the deque.
  3. Return the maximum answer found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<pair<int, int>> dq;
        int ans = INT_MIN;
        for (auto& pt : points) {
            int x = pt[0], y = pt[1];
            while (!dq.empty() && x - dq.front().second > k) dq.pop_front();
            if (!dq.empty()) ans = max(ans, y + x + dq.front().first);
            while (!dq.empty() && dq.back().first <= y - x) dq.pop_back();
            dq.emplace_back(y - x, x);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func findMaxValueOfEquation(points [][]int, k int) int {
    type pair struct{v, x int}
    dq := []pair{}
    ans := math.MinInt32
    for _, pt := range points {
        x, y := pt[0], pt[1]
        for len(dq) > 0 && x-dq[0].x > k {
            dq = dq[1:]
        }
        if len(dq) > 0 {
            if y+x+dq[0].v > ans {
                ans = y + x + dq[0].v
            }
        }
        for len(dq) > 0 && dq[len(dq)-1].v <= y-x {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, pair{y - x, x})
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        Deque<int[]> dq = new ArrayDeque<>();
        int ans = Integer.MIN_VALUE;
        for (int[] pt : points) {
            int x = pt[0], y = pt[1];
            while (!dq.isEmpty() && x - dq.peekFirst()[1] > k) dq.pollFirst();
            if (!dq.isEmpty()) ans = Math.max(ans, y + x + dq.peekFirst()[0]);
            while (!dq.isEmpty() && dq.peekLast()[0] <= y - x) dq.pollLast();
            dq.offerLast(new int[]{y - x, x});
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun findMaxValueOfEquation(points: Array<IntArray>, k: Int): Int {
        val dq = ArrayDeque<Pair<Int, Int>>()
        var ans = Int.MIN_VALUE
        for ((x, y) in points) {
            while (dq.isNotEmpty() && x - dq.first().second > k) dq.removeFirst()
            if (dq.isNotEmpty()) ans = maxOf(ans, y + x + dq.first().first)
            while (dq.isNotEmpty() && dq.last().first <= y - x) dq.removeLast()
            dq.addLast(y - x to x)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def findMaxValueOfEquation(self, points: list[list[int]], k: int) -> int:
        from collections import deque
        dq = deque()
        ans = float('-inf')
        for x, y in points:
            while dq and x - dq[0][1] > k:
                dq.popleft()
            if dq:
                ans = max(ans, y + x + dq[0][0])
            while dq and dq[-1][0] <= y - x:
                dq.pop()
            dq.append((y - x, x))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn find_max_value_of_equation(points: Vec<Vec<i32>>, k: i32) -> i32 {
        use std::collections::VecDeque;
        let mut dq = VecDeque::new();
        let mut ans = i32::MIN;
        for pt in points {
            let x = pt[0];
            let y = pt[1];
            while let Some(&(_, xi)) = dq.front() {
                if x - xi > k {
                    dq.pop_front();
                } else {
                    break;
                }
            }
            if let Some(&(v, _)) = dq.front() {
                ans = ans.max(y + x + v);
            }
            while let Some(&(v, _)) = dq.back() {
                if v <= y - x {
                    dq.pop_back();
                } else {
                    break;
                }
            }
            dq.push_back((y - x, x));
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findMaxValueOfEquation(points: number[][], k: number): number {
        const dq: [number, number][] = [];
        let ans = -Infinity;
        for (const [x, y] of points) {
            while (dq.length && x - dq[0][1] > k) dq.shift();
            if (dq.length) ans = Math.max(ans, y + x + dq[0][0]);
            while (dq.length && dq[dq.length-1][0] <= y - x) dq.pop();
            dq.push([y - x, x]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of points, since each point is pushed and popped from the deque at most once.
  • 🧺 Space complexity: O(n), for the deque storing candidate points.