Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Max Value of Equation solution and explanation

HardArrayHeap (Priority Queue)Monotonic QueueQueue7 min read45.0% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Max Value of Equation
11:23
Leetcode 1499. Max Value of EquationFraz · 11:23 · 14K viewsWatch on YouTube
7 more videos on this problem
  1. Leetcode 1499. Max Value of EquationFraz · 11:23 · 14K views
  2. LeetCode 1499. Max Value of EquationHappy Coding · 33:16 · 4K views
  3. 花花酱 LeetCode 1499. Max Value of Equation - 刷题找工作 EP340Hua Hua · 21:44 · 2K views
  4. 1499. Max Value of Equation (Leetcode Hard)Programming Live with Larry · 2:38 · 2K views
  5. Max Value of Equation || Arsh Goyal DSA Sheet Q25 || Arrays || Leetcode 1499 || Google || AmazonDSA Zindabad · 15:10 · 1K views
  6. Max Value of Equation | Leetcode #1499 | Interviewhelpinterviewhelp.io · 25:26 · 1K views
  7. 【每日一题】1499. Max Value of Equation, 7/7/2020Huifeng Guan · 17:20 · 766 views
  8. Leetcode 1499. Max Value of Equation (monotonic queue)LetsCode · 16:01 · 212 views

The 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.

Approach overview

Problem Overview: You are given points sorted by x. For any pair (i, j) where i < j and xj - xi ≤ k, maximize the equation yi + yj + |xi - xj|. Because the points are sorted, |xi - xj| becomes xj - xi, which lets you rearrange the formula into (yi - xi) + (yj + xj).

Approach 1: Optimized Brute Force with Binary Search (O(n²) worst case, O(1) space)

The constraint xj - xi ≤ k limits which previous points can pair with the current point. For each index j, use binary search to find the earliest index i such that the distance constraint still holds. Then iterate through that valid range and compute the equation value. The binary search reduces the search range compared to naive brute force, but the inner scan can still degrade to O(n), leading to O(n²) time in dense cases. This approach mainly helps you understand the constraint window before introducing more advanced data structures.

Approach 2: Heap-Based Sliding Window (O(n log n) time, O(n) space)

The equation can be rewritten as (yi - xi) + (yj + xj). While iterating through points as j, you only need the maximum value of (yi - xi) among points whose x distance from xj is at most k. Maintain a max heap storing pairs (yi - xi, xi). As you process each point, remove heap elements where xj - xi > k since they fall outside the valid window.

The top of the heap always gives the best candidate for (yi - xi). Combine it with (yj + xj) to update the answer. Then push the current point's (yj - xj) into the heap for future iterations. The heap ensures fast retrieval of the best candidate while the sliding window constraint is enforced dynamically. This approach uses concepts from sliding window and heap (priority queue) problems.

Alternative Optimization: Monotonic Queue (O(n) time, O(n) space)

A stronger optimization replaces the heap with a deque that maintains candidates in decreasing order of (yi - xi). Before adding a new point, remove elements from the front whose x distance exceeds k. Then remove elements from the back if their (yi - xi) value is smaller than the current one. The deque remains monotonic, so the front always holds the best candidate. This eliminates the log n heap operations and achieves linear time using a monotonic queue.

Recommended for interviews: The heap-based sliding window is the most common interview solution because it clearly demonstrates the algebraic transformation and window filtering. Explaining the brute force first shows understanding of the constraint. Implementing the heap or monotonic deque version proves you can optimize to near-linear time.

Approach 1: Heap-Based Sliding Window

This approach utilizes a max-heap to keep track of the maximum value of yi - xi for valid indices i, where valid means i is within the window of xj - xi <= k. This helps efficiently compute the possible maximum value of the equation yj + xj + (yi - xi).

from collections import deque

def find_max_value_of_equation(points, k):
    dq = deque()  # stores (y-x, x)
    max_value = float('-inf')

    for x, y in points:
        while dq and x - dq[0][1] > k:
            dq.popleft()
        if dq:
            max_value = max(max_value, dq[0][0] + x + y)
        while dq and dq[-1][0] <= y - x:
            dq.pop()
        dq.append((y - x, x))
    return max_value

points = [[1, 3], [2, 0], [5, 10], [6, -10]]
k = 1
print(find_max_value_of_equation(points, k))
import java.util.*;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        Deque<int[]> dq = new LinkedList<>(); // store pairs of (y-x, x)
        int maxValue = Integer.MIN_VALUE;
        for (int[] point : points) {
            while (!dq.isEmpty() && (point[0] - dq.peekFirst()[1]) > k) {
                dq.pollFirst();
            }
            if (!dq.isEmpty()) {
                maxValue = Math.max(maxValue, dq.peekFirst()[0] + point[0] + point[1]);
            }
            while (!dq.isEmpty() && dq.peekLast()[0] <= (point[1] - point[0])) {
                dq.pollLast();
            }
            dq.offerLast(new int[]{point[1] - point[0], point[0]});
        }
        return maxValue;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] points = {{1,3},{2,0},{5,10},{6,-10}};
        int k = 1;
        System.out.println(sol.findMaxValueOfEquation(points, k));
    }
}
#include <iostream>
#include <deque>
#include <vector>
using namespace std;

typedef pair<int, int> pii;

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<pii> dq; // store pairs of (y-x, x)
        int maxValue = INT_MIN;
        for (auto& p : points) {
            while (!dq.empty() && (p[0] - dq.front().second) > k) {
                dq.pop_front();
            }
            if (!dq.empty()) {
                maxValue = max(maxValue, dq.front().first + p[0] + p[1]);
            }
            while (!dq.empty() && dq.back().first <= (p[1] - p[0])) {
                dq.pop_back();
            }
            dq.emplace_back(p[1] - p[0], p[0]);
        }
        return maxValue;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> points = {{1,3},{2,0},{5,10},{6,-10}};
    int k = 1;
    cout << sol.findMaxValueOfEquation(points, k) << endl;
    return 0;
}
var findMaxValueOfEquation = function(points, k) {
    let deque = [];
    let maxValue = -Infinity;

    for(let [x, y] of points) {
        while(deque.length && x - deque[0][1] > k) {
            deque.shift();
        }
        if(deque.length) {
            maxValue = Math.max(maxValue, deque[0][0] + x + y);
        }
        while(deque.length && deque[deque.length - 1][0] <= y - x) {
            deque.pop();
        }
        deque.push([y - x, x]);
    }

    return maxValue;
};

const points = [[1, 3], [2, 0], [5, 10], [6, -10]];
const k = 1;
console.log(findMaxValueOfEquation(points, k));
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_POINTS 100000

typedef struct Point{
    int x, y;
} Point;

int cmp(const void *a, const void *b) {
    return ((Point*)a)->x - ((Point*)b)->x;
}

int findMaxValueOfEquation(Point* points, int pointsSize, int k) {
    int left = 0, right = 0, maxValue = INT_MIN;
    while (right < pointsSize) {
        while (left < right && points[right].x - points[left].x > k) {
            left++;
        }
        if (left < right) {
            int currentValue = points[right].y + points[right].x + points[left].y - points[left].x;
            if (currentValue > maxValue) maxValue = currentValue;
        }
        right++;
    }
    return maxValue;
}

int main() {
    Point points[] = {{1,3},{2,0},{5,10},{6,-10}};
    int k = 1;
    int pointsSize = sizeof(points)/sizeof(points[0]);
    printf("%d\n", findMaxValueOfEquation(points, pointsSize, k));
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public int FindMaxValueOfEquation(int[][] points, int k) {
        LinkedList<(int, int)> deque = new LinkedList<(int, int)>();
        int maxValue = int.MinValue;

        foreach (var point in points) {
            while (deque.Count > 0 && point[0] - deque.First.Value.Item2 > k) {
                deque.RemoveFirst();
            }
            if (deque.Count > 0) {
                maxValue = Math.Max(maxValue, deque.First.Value.Item1 + point[0] + point[1]);
            }
            while (deque.Count > 0 && deque.Last.Value.Item1 <= point[1] - point[0]) {
                deque.RemoveLast();
            }
            deque.AddLast((point[1] - point[0], point[0]));
        }

        return maxValue;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[][] points = { new int[]{1,3}, new int[]{2,0}, new int[]{5,10}, new int[]{6,-10} };
        int k = 1;
        Console.WriteLine(sol.FindMaxValueOfEquation(points, k));
    }
}

In Python, we're utilizing the collections module's deque to ensure O(1) complexity for pop and append operations. The implementation processes each point while ensuring that any point which would violate the xj - xi <= k condition is swiftly removed from the deque. This operation effectively limits the points considered in maximizing the expression to only those that are valid candidates for optimality.

Complexity

Time Complexity: O(n), as the deque allows efficient addition and removal operations per point.
Space Complexity: O(n), which accounts for the maximum potential size of the deque.

Try this approach in the editor

Approach 2: Optimized Brute Force with Binary Search

This approach uses binary search in combination with brute force to determine valid pairs by leveraging the sorted x-values, to effectively limit the search space for y-values which complement them. This approach isn't for optimal performance but demonstrates a valid attempt at improving a straightforward n^2 approach.

def find_max_value_of_equation(points, k):
    max_value = float('-inf')
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            if points[j][0] - points[i][0] > k:
                break
            current_value = points[i][1] + points[j][1] + points[j][0] - points[i][0]
            max_value = max(max_value, current_value)
    return max_value

points = [[1, 3], [2, 0], [5, 10], [6, -10]]
k = 1
print(find_max_value_of_equation(points, k))
import java.util.*;

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length && points[j][0] - points[i][0] <= k; j++) {
                int currentValue = points[i][1] + points[j][1] + points[j][0] - points[i][0];
                maxValue = Math.max(maxValue, currentValue);
            }
        }
        return maxValue;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] points = {{1,3},{2,0},{5,10},{6,-10}};
        int k = 1;
        System.out.println(sol.findMaxValueOfEquation(points, k));
    }
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int maxValue = INT_MIN;
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size() && points[j][0] - points[i][0] <= k; ++j) {
                int currentValue = points[i][1] + points[j][1] + points[j][0] - points[i][0];
                maxValue = max(maxValue, currentValue);
            }
        }
        return maxValue;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> points = {{1,3},{2,0},{5,10},{6,-10}};
    int k = 1;
    cout << sol.findMaxValueOfEquation(points, k) << endl;
    return 0;
}

Here, Python employs basic nested loops, iterating over potential points that obey the k boundary set by x values. Although not optimal regarding time complexity, it does illustrate the potential behind selectively choosing valid pairs in traditional brute force.

Complexity

Time Complexity: O(n²), as the outer loop sees each item matched by iterations inside conditional x boundaries.
Space Complexity: O(1), since no additional data structures are invoked that affect memory size in practice.

Try this approach in the editor

Approach 3: Default Approach

function findMaxValueOfEquation(points: number[][], k: number): number {
    let ans = -(1 << 30);
    const pq = new Heap<[number, number]>((a, b) => b[0] - a[0]);
    for (const [x, y] of points) {
        while (pq.size() && x - pq.top()[1] > k) {
            pq.pop();
        }
        if (pq.size()) {
            ans = Math.max(ans, x + y + pq.top()[0]);
        }
        pq.push([y - x, x]);
    }
    return ans;
}

type Compare<T> = (lhs: T, rhs: T) => number;

class Heap<T = number> {
    data: Array<T | null>;
    lt: (i: number, j: number) => boolean;
    constructor();
    constructor(data: T[]);
    constructor(compare: Compare<T>);
    constructor(data: T[], compare: Compare<T>);
    constructor(data: T[] | Compare<T>, compare?: (lhs: T, rhs: T) => number);
    constructor(
        data: T[] | Compare<T> = [],
        compare: Compare<T> = (lhs: T, rhs: T) => (lhs < rhs ? -1 : lhs > rhs ? 1 : 0),
    ) {
        if (typeof data === 'function') {
            compare = data;
            data = [];
        }
        this.data = [null, ...data];
        this.lt = (i, j) => compare(this.data[i]!, this.data[j]!) < 0;
        for (let i = this.size(); i > 0; i--) this.heapify(i);
    }

    size(): number {
        return this.data.length - 1;
    }

    push(v: T): void {
        this.data.push(v);
        let i = this.size();
        while (i >> 1 !== 0 && this.lt(i, i >> 1)) this.swap(i, (i >>= 1));
    }

    pop(): T {
        this.swap(1, this.size());
        const top = this.data.pop();
        this.heapify(1);
        return top!;
    }

    top(): T {
        return this.data[1]!;
    }
    heapify(i: number): void {
        while (true) {
            let min = i;
            const [l, r, n] = [i * 2, i * 2 + 1, this.data.length];
            if (l < n && this.lt(l, min)) min = l;
            if (r < n && this.lt(r, min)) min = r;
            if (min !== i) {
                this.swap(i, min);
                i = min;
            } else break;
        }
    }

    clear(): void {
        this.data = [null];
    }

    private swap(i: number, j: number): void {
        const d = this.data;
        [d[i], d[j]] = [d[j], d[i]];
    }
}
func findMaxValueOfEquation(points [][]int, k int) int {
	ans := -(1 << 30)
	hp := hp{}
	for _, p := range points {
		x, y := p[0], p[1]
		for hp.Len() > 0 && x-hp[0].x > k {
			heap.Pop(&hp)
		}
		if hp.Len() > 0 {
			ans = max(ans, x+y+hp[0].v)
		}
		heap.Push(&hp, pair{y - x, x})
	}
	return ans
}

type pair struct{ v, x int }

type hp []pair

func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
	a, b := h[i], h[j]
	return a.v > b.v
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
Try this approach in the editor

Complexity comparison

ApproachComplexity
Heap-Based Sliding Window

Time Complexity: O(n), as the deque allows efficient addition and removal operations per point.
Space Complexity: O(n), which accounts for the maximum potential size of the deque.

Optimized Brute Force with Binary Search

Time Complexity: O(n²), as the outer loop sees each item matched by iterations inside conditional x boundaries.
Space Complexity: O(1), since no additional data structures are invoked that affect memory size in practice.

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Optimized Brute Force with Binary SearchO(n²) worst caseO(1)Useful for understanding the distance constraint and validating the formula transformation
Heap-Based Sliding WindowO(n log n)O(n)General optimal solution using a priority queue to track the best (yi - xi)
Monotonic QueueO(n)O(n)Best theoretical performance when you maintain a decreasing deque of candidates

Frequently asked questions

Is Max Value of Equation easy or hard?

Max Value of Equation is classified as Hard because the key step is transforming the equation into (yi - xi) + (yj + xj). After that insight, you must combine sliding window constraints with a heap or monotonic queue to maintain the optimal candidate efficiently.

Max Value of Equation Python/Java solution

Most implementations iterate through the points while maintaining a heap of candidate values (yi - xi). Python solutions typically use heapq with negative values to simulate a max heap, while Java uses PriorityQueue with a custom comparator. Both implementations run in O(n log n) time.

How to solve Max Value of Equation in O(n)?

Use a monotonic deque that stores points in decreasing order of (yi - xi). While iterating through points, remove elements from the front if their x distance exceeds k, and remove smaller values from the back before inserting the current point. The front of the deque always provides the best candidate, giving a linear O(n) solution.

What is the best approach for Max Value of Equation?

The most practical solution uses a heap-based sliding window. Rewrite the equation as (yi - xi) + (yj + xj) and keep a max heap of (yi - xi) values for points within distance k. While iterating through points, remove outdated entries whose x distance exceeds k. This achieves O(n log n) time and O(n) space.

Is Max Value of Equation asked at Google/Amazon/Meta?

Max Value of Equation is a common hard-level interview problem that appears in companies focusing on algorithmic optimization such as Google, Meta, and Amazon. It tests sliding window reasoning, algebraic transformation of equations, and advanced data structures like heaps or monotonic queues.

What data structure is used in Max Value of Equation?

The standard solution uses a max heap (priority queue) combined with a sliding window constraint. A more optimized implementation replaces the heap with a monotonic deque to maintain the best (yi - xi) candidate efficiently.

What is the time complexity of Max Value of Equation?

The optimal heap-based solution runs in O(n log n) time because each point is pushed and popped from the heap at most once. A monotonic deque optimization can reduce this to O(n). Space complexity is O(n) for storing candidate points in the window.

Comments

Next problem · similarCount Pairs in Two ArraysMedium
Now write it yourselfClose this page and solve Max Value of Equation in the editor, without looking.
Practise Max Value of Equation