Skip to main content

Sliding Window

Max Value of Equation Solution In C++/Python/java/JS

Problem Description

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

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.


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
  • -10^8 <= xi, yi <= 10^8
  • 0 <= k <= 2 * 10^8
  • xi < xj for all 1 <= i < j <= points.length
  • xi form a strictly increasing sequence.
💡
Try it Yourself First
We need to maximize the equation value while ensuring the x-coordinates satisfy a given constraint. Using a max-heap, we efficiently track valid points, removing those that exceed the allowed distance. This optimizes the search and ensures we find the maximum value efficiently.

Brute Force Approach

Intuition

Our goal is to maximize the equation yi + yj + |xi - xj| while ensuring |xi - xj| ≤ k. Since the array is sorted by x-values, we know xi < xj, which simplifies the absolute difference to xj - xi. This allows us to rewrite the equation as (yi - xi) + (yj + xj).

A straightforward way to solve this is by iterating through all possible pairs (i, j) and checking if they satisfy the constraint |xi - xj| ≤ k. If they do, we compute the equation’s value and track the maximum. Since there are O(n²) possible pairs, this results in O(n²) time complexity, making it inefficient for large inputs.

To implement this, we start with the first point (xi, yi) and iterate over all subsequent points (xj, yj). For each pair, we verify whether xj - xi ≤ k and, if the condition holds, compute (yi - xi) + (yj + xj). We maintain a variable to track the highest value encountered so far. As we continue iterating, we compare and update this maximum whenever a new valid pair is found.

This approach ensures that every possible combination is examined and guarantees correctness. However, because it exhaustively checks all pairs, it becomes computationally expensive as n grows.

Approach

Step 1: Iterate Through Each Point

  • Start by iterating through each point i in the points array.

Step 2: Check All Subsequent Points

  • For each i, iterate over all subsequent points j such that j > i.

Step 3: Verify Constraint

  • Check if the pair (xi, yi) and (xj, yj) satisfies the given condition |xi - xj| ≤ k.

Step 4: Compute the Equation

  • If the constraint is met, compute the equation value:
    yi+yj+∣xi−xj∣

Step 5: Track Maximum Value

  • Keep a variable ans to track the highest computed value across all valid pairs.

Step 6: Return the Maximum Value

  • After iterating through all pairs, return the maximum value found.

Dry Run

Input:

  • points = [[1,3],[2,0],[5,10],[6,-10]], k = 1

Step 1: List All Possible Pairs

  • We iterate over each (i, j) pair and check if |xi - xj| ≤ k. If valid, we compute: yi+yj+∣xi−xj∣

Step 2: Compute Values for Valid Pairs

Pair (1,3) and (2,0)

  • xi = 1, yi = 3, xj = 2, yj = 0
  • |1 - 2| = 1 (valid as 1 ≤ k)
  • Compute: 3 + 0 + 1 = 4
  • Max Value so far = 4

Pair (1,3) and (2,0)

  • xi = 1, yi = 3, xj = 2, yj = 0
  • |1 - 2| = 1 (valid as 1 ≤ k)
  • Compute: 3 + 0 + 1 = 4
  • Max Value so far = 4

Pair (5,10) and (6,-10)

  • xi = 5, yi = 10, xj = 6, yj = -10
  • |5 - 6| = 1 (valid as 1 ≤ k)
  • Compute: 10 + (-10) + 1 = 1
  • Max Value remains 4

Step 3: Return Maximum Computed Value

  • The highest computed value is 4.

Final Output: 4

Code for All Languages
C++ 
// Approach: Brute Force  
// Language: C++  

#include <iostream>  
#include <vector>  
#include <climits>  

using namespace std;  

class Solution {  
public:  

    // Step 1: Function to find the maximum value of the equation  
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {  

        // Get the number of points  
        int n = points.size();  

        // Initialize the answer with the minimum integer value  
        int ans = INT_MIN;  

        // Step 2: Iterate over each point i  
        for (int i = 0; i < n - 1; i++) {  

            // Step 3: Iterate over each subsequent point j  
            for (int j = i + 1; j < n && abs(points[i][0] - points[j][0]) <= k; j++) {  

                // Compute the equation value  
                int sum = points[i][1] + points[j][1] + abs(points[i][0] - points[j][0]);  

                // Update the maximum value found so far  
                ans = max(ans, sum);  
            }  
        }  

        // Step 4: Return the maximum computed value  
        return ans;  
    }  
};

Java 
// Approach: Brute Force  
// Language: Java  

import java.util.*;  

class Solution {  

    // Step 1: Function to find the maximum value of the equation  
    public int findMaxValueOfEquation(int[][] points, int k) {  

        // Get the number of points  
        int n = points.length;  

        // Initialize the answer with the minimum integer value  
        int ans = Integer.MIN_VALUE;  

        // Step 2: Iterate over each point i  
        for (int i = 0; i < n - 1; i++) {  

            // Step 3: Iterate over each subsequent point j  
            for (int j = i + 1; j < n && Math.abs(points[i][0] - points[j][0]) <= k; j++) {  

                // Compute the equation value  
                int sum = points[i][1] + points[j][1] + Math.abs(points[i][0] - points[j][0]);  

                // Update the maximum value found so far  
                ans = Math.max(ans, sum);  
            }  
        }  

        // Step 4: Return the maximum computed value  
        return ans;  
    }  
}

Python 
# Approach: Brute Force  
# Language: Python  

class Solution(object):  
    def findMaxValueOfEquation(self, points, k):  
        """  
        :type points: List[List[int]]  
        :type k: int  
        :rtype: int  
        """  

        # Step 1: Get the number of points  
        n = len(points)  

        # Initialize the answer with negative infinity  
        ans = float('-inf')  

        # Step 2: Iterate over each point i  
        for i in range(n - 1):  

            # Step 3: Iterate over each subsequent point j  
            for j in range(i + 1, n):  

                # Check if the condition |xi - xj| <= k holds  
                if abs(points[i][0] - points[j][0]) <= k:  

                    # Compute the equation value  
                    sum_value = points[i][1] + points[j][1] + abs(points[i][0] - points[j][0])  

                    # Update the maximum value found so far  
                    ans = max(ans, sum_value)  

        # Step 4: Return the maximum computed value  
        return ans

Javascript 
// Approach: Brute Force  
// Language: JavaScript  

var findMaxValueOfEquation = function(points, k) {  
    // Step 1: Get the number of points  
    let n = points.length;  

    // Initialize the answer with negative infinity  
    let ans = -Infinity;  

    // Step 2: Iterate over each point i  
    for (let i = 0; i < n - 1; i++) {  

        // Step 3: Iterate over each subsequent point j  
        for (let j = i + 1; j < n && Math.abs(points[i][0] - points[j][0]) <= k; j++) {  

            // Compute the equation value  
            let sum = points[i][1] + points[j][1] + Math.abs(points[i][0] - points[j][0]);  

            // Update the maximum value found so far  
            ans = Math.max(ans, sum);  
        }  
    }  

    // Step 4: Return the maximum computed value  
    return ans;  
};

Time Complexity Analysis: O(n²)

Let n be the number of points in the input array.

  • The algorithm iterates over each point i, and for each i, it iterates over all subsequent points j such that |xi - xj| ≤ k.
  • In the worst case, the inner loop runs for nearly O(n) iterations for each i, leading to an overall complexity of O(n²).
  • Since there are no additional optimizations (such as data structures to efficiently track the maximum values), the brute-force approach results in O(n²) time complexity.

Final Time Complexity: O(n^2)

Space Complexity Analysis: O(1)

  • The algorithm only uses a few integer variables (n, ans, i, j, sum_value) to keep track of indices and maximum values.
  • No additional data structures (such as heaps, queues, or extra arrays) are used.
  • Since the space usage does not grow with the input size n, the space complexity remains O(1).

Final Space Complexity:O(1).

The brute-force approach checks all pairs, which is inefficient. Using a max-heap, we track valid points dynamically, removing those that exceed the distance constraint. This ensures we efficiently find the maximum value while reducing unnecessary computations.

Optimal Approach

Intuition

The brute-force approach checks all possible pairs of points, leading to O(n^2) time complexity, which is inefficient for large inputs. To optimize, we can use a Max-Heap (Priority Queue) to maintain the best candidates while iterating through the points.

The given equation is:Equation Value = (yi + yj) + |xi - xj|

This can be written as : (yi-xi) + (yj + xj)

This transformation helps break the problem into two parts. We need to find a previous point (xi,yi) such that xj-xi ≤k, and among such points, we must maximize (yi-xi) to get the optimal sum.

Instead of checking every previous point explicitly, we use a Max-Heap (Priority Queue) to store the best candidates efficiently. The heap stores pairs (yi-xi,xi) . At each step, we remove outdated points that do not satisfy xj-xi≤k. The top of the heap gives the best possible yi-xi for the current (xj,yj).We compute the equation value using this value, then push (yj-xj,xj) into the heap for future calculations.

This approach ensures that instead of iterating over all previous points, we maintain only valid points in the heap, reducing the complexity to O(nlogn). This is much faster than the brute-force approach while still guaranteeing the optimal result.

Approach

Step 1: Initialize a Max-Heap

  • Create an empty max-heap (priority queue) to store pairs of the form
    (yi-xi,xi).
  • This helps efficiently track the best possible candidate for maximizing the equation.

Step 2: Iterate Through Each Point

  • For each point (xj,yj) in the given array, process it one by one.

Step 3: Remove Invalid Points
Remove points from the heap where |xj-xi|>k.
This ensures that only valid points (satisfying the constraint) remain in the heap.

Step 4: Compute the Maximum Value

  • If the heap is not empty after removing invalid points:
  • Extract the top element from the heap, which gives the largest (yi−xi).
  • Compute the equation using:
  • Equation Value=(yi−xi)+(yj+xj)
  • Update the maximum result found so far.

Step 5: Push the Current Point into the Heap

  • Add the current (yj-xj,xj) into the heap for future computations.

Step 6: Return the Maximum Value

  • After processing all points, return the highest equation value found.

Dry Run

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1

Expected Output: 4

Step 1: Initialize Max-Heap

  • We start with an empty max-heap to store pairs (y_i - x_i, x_i).

Step 2: Iterate Through Each Point

  • We process each point (x_j, y_j) and maintain the heap while ensuring |x_j - x_i| ≤ k.

Processing (1,3)

  • The heap is empty, so nothing to remove.
  • Add (3 - 1, 1) → (2,1) to the heap.
  • Heap: [(2, 1)]

Processing (2,0)

  • Remove invalid points:
  • |2 - 1| = 1 ≤ k, so no points are removed.
  • Compute equation with top heap element (2,1):
  • yj+xj+(yi−xi)=0+2+2=4
  • Update max value: ans = max(-∞, 4) = 4
  • Add (0 - 2, 2) → (-2,2) to the heap.
  • Heap: [(2,1), (-2,2)]

Processing (5,10)

  • Remove invalid points:
  • |5 - 1| = 4 > k, remove (2,1).
  • |5 - 2| = 3 > k, remove (-2,2).
  • Heap is empty, so no computation.
  • Add (10 - 5, 5) → (5,5) to the heap.
  • Heap: [(5,5)]

Processing (6,-10)

  • Remove invalid points:
  • |6 - 5| = 1 ≤ k, so no points are removed.
  • Compute equation with top heap element (5,5):
  • −10+6+5=1
  • Update max value: ans = max(4, 1) = 4
  • Add (-10 - 6, 6) → (-16,6) to the heap.
  • Heap: [(5,5), (-16,6)]

Final Output: 4

Code for All Languages
C++ 
// Approach: Max Heap (Priority Queue) to Find Maximum Value of Equation  
// Language: C++  

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    // Step 1: Initialize Priority Queue (Max-Heap)
    // The heap stores pairs of (yi - xi, xi), maintaining the maximum yi - xi at the top.
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, int>> pq; // Max-Heap (yi - xi, xi)
        int res = INT_MIN;

        // Step 2: Iterate Through Each Point
        for (auto& point : points) {
            int xj = point[0], yj = point[1];

            // Step 3: Remove Invalid Points
            // Remove elements from the heap where |xj - xi| > k
            while (!pq.empty() && xj - pq.top().second > k) {
                pq.pop();
            }

            // Step 4: Compute the Maximum Value if the Heap is Not Empty
            if (!pq.empty()) {
                int yi_minus_xi = pq.top().first;
                int xi = pq.top().second;

                // Compute equation: yj + xj + (yi - xi)
                res = max(res, yi_minus_xi + xj + yj);
            }

            // Step 5: Push the Current Point into the Heap
            pq.push({yj - xj, xj});
        }

        // Step 6: Return the Maximum Value Found
        return res;
    }
};

Java 
// Approach: Max Heap (Priority Queue) to Find Maximum Value of Equation  
// Language: Java  
class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        // Step 1: Initialize Priority Queue (Max-Heap)
        // The heap stores pairs (yi - xi, xi), keeping the maximum yi - xi at the top.
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> 
            b.getKey() - a.getKey()); // Max-Heap based on yi - xi
        int res = Integer.MIN_VALUE;

        // Step 2: Iterate Through Each Point
        for (int[] point : points) {
            int xj = point[0], yj = point[1];

            // Step 3: Remove Invalid Points
            // Remove elements from the heap where |xj - xi| > k
            while (!pq.isEmpty() && xj - pq.peek().getValue() > k) {
                pq.poll();
            }

            // Step 4: Compute the Maximum Value if the Heap is Not Empty
            if (!pq.isEmpty()) {
                int yi_minus_xi = pq.peek().getKey();
                int xi = pq.peek().getValue();

                // Compute equation: yj + xj + (yi - xi)
                res = Math.max(res, yi_minus_xi + xj + yj);
            }

            // Step 5: Push the Current Point into the Heap
            pq.offer(new Pair<>(yj - xj, xj));
        }

        // Step 6: Return the Maximum Value Found
        return res;
    }
}

Python 
# Approach: Max Heap (Priority Queue) to Find Maximum Value of Equation  
# Language: Python  

import heapq

class Solution(object):
    def findMaxValueOfEquation(self, points, k):
        """
        :type points: List[List[int]]
        :type k: int
        :rtype: int
        """

        # Step 1: Initialize Max-Heap (using min-heap with negative values)
        # The heap stores (-yi + xi, xi) so that the maximum yi - xi is at the top
        max_heap = []
        res = float('-inf')

        # Step 2: Iterate Through Each Point
        for xj, yj in points:

            # Step 3: Remove Invalid Points
            # Remove elements from the heap where |xj - xi| > k
            while max_heap and xj - max_heap[0][1] > k:
                heapq.heappop(max_heap)

            # Step 4: Compute the Maximum Value if the Heap is Not Empty
            if max_heap:
                yi_minus_xi, xi = max_heap[0]
                # Compute equation: yj + xj + (yi - xi)
                res = max(res, -yi_minus_xi + xj + yj)

            # Step 5: Push the Current Point into the Heap
            heapq.heappush(max_heap, (-(yj - xj), xj))  # Store negative to simulate max-heap

        # Step 6: Return the Maximum Value Found
        return res

Javascript 
/**
 * Approach: Max Heap (Priority Queue) to Find Maximum Value of Equation
 * Language: JavaScript
 */

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number}
 */
var findMaxValueOfEquation = function(points, k) {
    // Step 1: Initialize Max Heap (using Min Heap with negative values)
    // The heap stores [yi - xi, xi] so that the maximum yi - xi is at the top
    let maxHeap = [];
    let res = -Infinity;

    // Step 2: Iterate Through Each Point
    for (let [xj, yj] of points) {
        
        // Step 3: Remove Invalid Points
        // Remove elements from the heap where |xj - xi| > k
        while (maxHeap.length > 0 && xj - maxHeap[0][1] > k) {
            maxHeap.shift(); // Remove the top element
        }

        // Step 4: Compute the Maximum Value if the Heap is Not Empty
        if (maxHeap.length > 0) {
            let [yiMinusXi, xi] = maxHeap[0];
            // Compute equation: yj + xj + (yi - xi)
            res = Math.max(res, yiMinusXi + xj + yj);
        }

        // Step 5: Push the Current Point into the Heap
        maxHeap.push([yj - xj, xj]);
        // Maintain the max heap order (sorting in descending order)
        maxHeap.sort((a, b) => b[0] - a[0]);
    }

    // Step 6: Return the Maximum Value Found
    return res;
};

Time Complexity Analysis: O(n log n)

Let n be the number of points in the input array and k be the given constraint.

Heap Operations (Insertion & Removal): O(log n)

  • Each point is pushed into the priority queue once, which takes O(log n).
  • In the worst case, each point may also be removed once, taking another O(log n).

Iteration Over Points: O(n)

  • We iterate through all n points, and for each point, we might perform heap operations.

Overall Complexity: O(n log n)

  • Since each insertion and removal operation costs O(log n) and happens at most n times, the total complexity is O(n log n).

Thus, the overall time complexity of the algorithm is O(n log n).

Space Complexity Analysis: O(n)

Priority Queue Storage (O(n))

  • The priority queue (max-heap) stores at most n elements in the worst case (if no elements are removed due to the distance constraint k).
  • Each entry in the priority queue consists of a pair (y_i - x_i, x_i), which takes O(1) space per element.
  • Thus, the total space required for the priority queue is O(n).

Auxiliary Space (O(1))

  • Apart from the priority queue, only a few extra integer variables are used (like res for storing the maximum result).
  • No additional data structures or recursion is used.

Final Space Complexity:O(n)

  • The dominant factor in space usage is the priority queue, which can grow to O(n) in the worst case. Thus, the overall space complexity remains O(n).

Similar Problems

Now we have successfully tackled this problem, let’s try these similar problems.

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.Note that it is the kth largest element in the sorted order, not the kth distinct element.

Find Median from Data Stream

This problem requires continuously finding the median of a growing data stream. It uses two heaps (a max-heap for the left half and a min-heap for the right half) to efficiently balance and retrieve the median in O(log n) insertion and O(1) retrieval time, similar to how we maintain the k-th largest element in a min-heap.