Skip to main content
Talentd

Max Value of Equation - Solution & Explanation

HardArrayQueueSliding WindowHeap (Priority Queue)15 min readAsked at: Google
Practice this problem

Problem Statement

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

In C, we use a simple array to represent our points and a dual-pointer strategy to simulate the sliding window effect. By iterating over the sorted array with two pointers, we ensure each point is considered within a defined window size & k. Whenever window restrictions are violated, we adjust the left pointer. This ensures our resultant equation meets the condition xj - xi <= k, maximizing the value.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of points. We essentially scan through the points with the right pointer and adjust the left pointer as needed.
Space Complexity: O(1), as we are using constant space.

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.

This refined brute force approach makes use of a nested loop. By exploiting the sorted x-coordinates, it employs the immediate current loop index to avoid unnecessary calculations past the point where x-compliance is violated. This sparks efficiency beyond basic brute force.

Code

C++JavaPython

C++

Java

Python

Complexity

Time Complexity: O(n²), since each element is checked against subsequent ones up to x constraint.
Space Complexity: O(1), as no additional data structure is utilized.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Heap-Based Sliding Window

Time Complexity: O(n), where n is the number of points. We essentially scan through the points with the right pointer and adjust the left pointer as needed.
Space Complexity: O(1), as we are using constant space.

Optimized Brute Force with Binary Search

Time Complexity: O(n²), since each element is checked against subsequent ones up to x constraint.
Space Complexity: O(1), as no additional data structure is utilized.

Default Approach—

Detailed 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

Video Solution

Leetcode 1499. Max Value of Equation • Fraz • 14,622 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Max Value of Equation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Pairs in Two Arrays