Max Value of Equation — Hard Problem & Solution

You are given points, where points[i] = [xi, yi], sorted by x in strictly increasing order, and an integer k.

Difficulty: Hard
Topics: Arrays, Sliding Window, Monotonic Queue
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given points, where points[i] = [xi, yi], sorted by x in strictly increasing order, and an integer k.

Return the maximum value of yi + yj + |xi - xj| over all pairs i < j with |xi - xj| <= k.

At least one such pair is guaranteed to exist.

Example 1

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
Output: 4
Explanation: Pairing (1,3) with (2,0) gives 3 + 0 + 1 = 4; the pair (5,10),(6,-10) gives 1.

Example 2

Input: points = [[0,0],[3,0],[9,2]], k = 3
Output: 3
Explanation: Only (0,0) and (3,0) are within k, giving 0 + 0 + 3 = 3.

Example 3

Input: points = [[-19,9],[-15,-19],[-5,-8]], k = 10
Output: -6
Explanation: (-19,9) with (-15,-19) gives 9 - 19 + 4 = -6.

Constraints

2 <= points.length <= 100000
-100000 <= xi, yi <= 100000
xi < xj for all i < j
0 <= k <= 200000

How to solve Max Value of Equation

Sorted x removes the absolute value, and the expression splits into a part that depends only on j and a part that depends only on i. The task becomes a sliding-window maximum of yi - xi, which is the textbook monotonic-deque problem.

Approach

Keep a deque of indices whose y - x values are strictly decreasing from front to back.
For each j, pop from the front while xj - x[front] > k — those points have fallen out of the window.
The front now holds the best yi - xi in range, so the candidate answer is yj + xj + (y[front] - x[front]).
Before pushing j, pop from the back while the back's y - x is at most yj - xj — it can never win again.

Why it works

A point that is both older and has a smaller y - x than a newer point is dominated: it leaves the window sooner and is worth less, so discarding it loses nothing. That leaves a decreasing deque whose front is the window maximum. Each index is pushed and popped once, giving linear total work.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Evicting from the front after reading the candidate uses points that are out of range.
The answer can be negative, so initialising best to 0 is wrong — start from negative infinity.
Pushing j before computing the candidate would let a point pair with itself.

Reference solution

Python

from typing import List

def findMaxValueOfEquation(points: List[List[int]], k: int) -> int:
    dq = []
    head = 0
    best = None
    for j in range(len(points)):
        xj, yj = points[j][0], points[j][1]
        while head < len(dq) and xj - points[dq[head]][0] > k:
            head += 1
        if head < len(dq):
            i = dq[head]
            v = yj + xj + points[i][1] - points[i][0]
            if best is None or v > best:
                best = v
        cur = yj - xj
        while head < len(dq) and points[dq[-1]][1] - points[dq[-1]][0] <= cur:
            dq.pop()
        dq.append(j)
    return best

JavaScript

var findMaxValueOfEquation = function(points, k) {
    var dq = [];
    var head = 0;
    var best = -Infinity;
    for (var j = 0; j < points.length; j++) {
        var xj = points[j][0], yj = points[j][1];
        while (head < dq.length && xj - points[dq[head]][0] > k) head++;
        if (head < dq.length) {
            var i = dq[head];
            var v = yj + xj + points[i][1] - points[i][0];
            if (v > best) best = v;
        }
        var cur = yj - xj;
        while (head < dq.length && points[dq[dq.length - 1]][1] - points[dq[dq.length - 1]][0] <= cur) dq.pop();
        dq.push(j);
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue