Max Value of Equation

Hard
622.

Max Value of Equation

Max Value of Equation is a hard coding problem on arrays, sliding window and monotonic queue, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number}
 */
var findMaxValueOfEquation = function(points, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Max Value of Equation — Solution in Python, Java & C++

Max Value of Equation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Max Value of Equation is a hard coding problem on arrays, sliding window and monotonic queue, asked in Amazon, Google and Meta interviews.

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

Hints for Max Value of Equation

  1. Hint 1

    Because x is increasing, i < j means xi < xj, so |xi - xj| is just xj - xi.

  2. Hint 2

    Rewrite the objective as (yj + xj) + (yi - xi). The first bracket depends only on j.

  3. Hint 3

    So for each j you want the largest yi - xi among the i still inside the window xj - xi <= k — a sliding-window maximum, which a monotonic deque answers in O(1) amortised.

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

  1. Keep a deque of indices whose y - x values are strictly decreasing from front to back.
  2. For each j, pop from the front while xj - x[front] > k — those points have fallen out of the window.
  3. The front now holds the best yi - xi in range, so the candidate answer is yj + xj + (y[front] - x[front]).
  4. 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

Java

public static int findMaxValueOfEquation(int[][] points, int k) {
    int n = points.length;
    int[] dq = new int[n];
    int head = 0, tail = 0;
    long best = Long.MIN_VALUE;
    for (int j = 0; j < n; j++) {
        int xj = points[j][0], yj = points[j][1];
        while (head < tail && xj - points[dq[head]][0] > k) head++;
        if (head < tail) {
            int i = dq[head];
            long v = (long) yj + xj + points[i][1] - points[i][0];
            if (v > best) best = v;
        }
        int cur = yj - xj;
        while (head < tail && points[dq[tail - 1]][1] - points[dq[tail - 1]][0] <= cur) tail--;
        dq[tail++] = j;
    }
    return (int) best;
}

C++

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    int n = (int) points.size();
    vector<int> dq(n);
    int head = 0, tail = 0;
    long long best = LLONG_MIN;
    for (int j = 0; j < n; j++) {
        int xj = points[j][0], yj = points[j][1];
        while (head < tail && xj - points[dq[head]][0] > k) head++;
        if (head < tail) {
            int i = dq[head];
            long long v = (long long) yj + xj + points[i][1] - points[i][0];
            if (v > best) best = v;
        }
        int cur = yj - xj;
        while (head < tail && points[dq[tail - 1]][1] - points[dq[tail - 1]][0] <= cur) tail--;
        dq[tail++] = j;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sliding Window Technique