1499. Max Value of Equation

HardQueueArraySliding WindowMonotonic QueueHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an array of points, each containing a pair of coordinates [x, y] that represent points on a 2D plane. These points are sorted according to their x-coordinate values, ensuring that x[i] < x[j] for any two points points[i] and points[j] where i < j. Along with this array, you're also given an integer k.

Your task is to find and return the maximum value obtained from the equation y[i] + y[j] + |x[i] - x[j]| for any two different points, provided that the distance between these points in x-direction (|x[i] - x[j]|) is less than or equal to k.

It's guaranteed that you'll be able to find at least one pair of points fulfilling the condition |x[i] - x[j]| <= k.

In essence, you need to find a pair of points not further away from each other than k units along the x-axis, such that the given equation yields the maximum result.

Intuition

The core concept of the solution lies in understanding that we want to maximize the sum y[i] + y[j] + |x[i] - x[j]|, and that the absolute value |x[i] - x[j]| can simply be considered as x[j] - x[i] since the points are sorted by x-coordinate. Therefore, the equation simplifies to y[i] + y[j] + x[j] - x[i]. This can be rearranged to (y[i] - x[i]) + (y[j] + x[j]).

A crucial observation here is that for any point j, we want to find a point i with the maximum possible value of y[i] - x[i]. Such a point i should also be within the distance k from point j along the x-axis. To efficiently find this point i for each point j, we can use a queue to keep potential candidates of point i that are within the distance k from the current point j.

The goal is to maintain a monotonic queue where the value of y[i] - x[i] is in decreasing order (because if there is any i such that y[i] - x[i] is smaller than the last element in the queue, then it will never be the candidate to produce the maximum sum, as there will be another point with a larger y - x value and closer to the current j).

Let's breakdown the algorithm implemented in the solution code:

  1. Initialize ans with the smallest number possible (-inf), to store the maximum value of the equation.
  2. Initialize an empty deque q, where we will maintain our candidates for the maximum (y[i] - x[i]).
  3. Iterate through each point (x, y) in the points list:
    • While the deque is not empty and the x-distance from the current point to the front of the deque is greater than k, remove the front of the deque. This is because the point at the front of the deque is too far away to consider for the current point j.
    • If there is still any point left in the deque after the previous step, update the ans with the maximum of ans and the sum of the current y, x, and the value at the front of the deque (which represents the maximum (y[i] - x[i]) for a point within distance k).
    • While the deque is not empty and the value of (y - x) for the current point is greater than or equal to the value at the back of the deque, pop the back. This is because the new point is a better candidate since it provides a larger or equal value of y - x and is closer to future points j.
    • Finally, add the current point (x, y) to the deque as a candidate for future points.
  4. After iterating through all points, return ans as the result.

The solution efficiently uses a deque to keep the best candidate points for the maximum sum, updating the possible maximum with each point it examines and maintaining the deque according to the constraints given.

Learn more about Queue, Sliding Window, Monotonic Queue and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which two pointer technique does Quick Sort use?

Solution Approach

The solution utilizes a deque, which is a double-ended queue that supports addition and removal of elements from both ends in O(1) time complexity. This data structure is perfect for our needs because it allows us to maintain the candidates for points i that will potentially maximize our equation, while also enabling us to efficiently add new candidates and remove the old ones that are no longer in contention.

Here's the implementation explained step by step:

  1. Initialize ans with -inf, which acts as a placeholder for the maximum value of our equation as we go through each point.
  2. Initialize an empty deque q to maintain the candidate points i.

The deque q will store tuples (x, y) representing the points and will maintain them in a way where the value of y - x is in decreasing order.

  1. Begin a loop to go through each point (x, y) in the sorted points list:

    • First, we remove points from the front of the deque that are farther away than k from our current point x. This is done with a while loop that checks if the deque is not empty and the current x minus the x of the point at the front of the deque is greater than k, and if so, it removes the front point.
    • Next, if there are still points left in the deque after the cleanup, we calculate the value of the equation for the point j and the point i located at the front of the deque, which has the maximized value of y[i] - x[i]. We update ans with the maximum value between the existing ans and the newly calculated sum.
    • Then, we need to insert the current point (x, y) into the deque. Before doing that, we remove all points from the back of the deque that are worse candidates than the current one. A worse candidate is a point whose y - x is less than or equal to the y - x of the current point. This is because the current point is either equidistant or closer to all future points j, making the deque points with a smaller y - x irrelevant.
    • Finally, we add the current point (x, y) to the back of the deque, as it is now a candidate for future points.

  2. After the loop concludes, all pairs of points that could potentially satisfy our constraints have been considered, and ans contains the maximum value found.

In summary, by maintaining a list of candidate points in a deque and using a greedy approach to keep only the best candidates as we iterate through the points, the code ensures that we can find the maximum value of the equation y[i] + y[j] + |x[i] - x[j]| efficiently, where the absolute difference between x[i] and x[j] is at most k.

The approach effectively combines the monotonic deque pattern with the greedy algorithmic paradigm to tackle the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Consider the array of points points = [[1,3],[2,0],[5,10],[6,-10]] and k = 1.

According to our problem, we are looking for maximum value obtained from the equation y[i] + y[j] + |x[i] - x[j]|, where |x[i] - x[j]| is less than or equal to k.

Let's process each point and follow the described approach using a deque (denoted as q here):

  1. Our initial value of ans is -infinity because we haven't started, and q is empty.

  2. We examine the first point:

    • points[0] = [1,3]
    • q is still empty, so we just add (x[0], y[0] - x[0]) = (1, 2) to q.

  3. Moving to the second point:

    • points[1] = [2,0]
    • Before adding the point to q, remove points from q whose x-coordinate difference is more than k. Currently, point [1,3] is within k, so we keep it.
    • Consider the value for this point [2,0] using the point we have in q: ans = max(ans, y[1] + q.front(y-x) + x[1]) which would be 0 + 2 + 2 = 4.
    • Now, ensure current point's y-x is maintained in q. 0-2 = -2 < 2, so q doesn't change.
    • The deque q now contains [(1, 2), (2, -2)].

  4. Now, for the third point:

    • points[2] = [5,10]
    • The difference between x[2] and x[0] is more than k, so we remove the first point from q.
    • The deque q is now [(2, -2)].
    • Calculate ans: ans = max(ans, y[2] + q.front(y-x) + x[2]) which would be 10 - 2 + 5 = 13.
    • The current point [5,10] has y-x of 10 - 5 = 5 which is greater than -2, so we remove (2, -2) from the deque q and insert the current point.
    • The deque q updates to [(5, 5)].

  5. Finally, for the fourth point:

    • points[3] = [6,-10]
    • The difference between x[3] and x[2] is 1 which is within k. We don't remove anything from q.
    • Calculate ans: ans = max(ans, y[3] + q.front(y-x) + x[3]) which would be -10 + 5 + 6 = 1. However, the ans is already 13 from the previous step which is greater.
    • Add the current point [6,-10] with value y-x = (-10 - 6) = -16 to the deque q. Since -16 is less than 5, it's added but will not affect the ans.

We've now considered all points, and the maximum value found for ans is 13.

The final ans we return is 13, which is the maximum sum we calculated from the provided points, given the conditions of the problem.

Solution Implementation

1from collections import deque
2from math import inf
3
4class Solution:
5    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
6        # Initialize the answer to negative infinity to find the max value later
7        max_value = -inf
8      
9        # Use a deque to keep track of potential candidates for maximum value
10        candidates = deque()
11      
12        # Iterate through each point in the given list of points
13        for x, y in points:
14            # Remove any (x, y) from the deque where the current x 
15            # minus the candidate's x is greater than k (outside the window)
16            while candidates and x - candidates[0][0] > k:
17                candidates.popleft()
18          
19            # If the deque is not empty, update max_value with the maximum value found
20            # considering the equation yi + yj + |xi - xj| with current point and 
21            # candidate at the front of the deque
22            if candidates:
23                max_value = max(max_value, x + y + candidates[0][1] - candidates[0][0])
24          
25            # Ensure that deque holds the candidates in decreasing order of their value for y - x
26            # Pop out the last element if it's smaller than the incoming element
27            while candidates and y - x >= candidates[-1][1] - candidates[-1][0]:
28                candidates.pop()
29          
30            # Append the current point as a candidate for future computations
31            candidates.append((x, y))
32      
33        # Return the computed max value of the equation
34        return max_value
35
1class Solution {
2    public int findMaxValueOfEquation(int[][] points, int k) {
3        // Initialize answer to a very small number to ensure any valid equation will be larger.
4        int answer = Integer.MIN_VALUE;
5      
6        // Use a deque to maintain potential candidates for (xi, yi) in a sliding window fashion.
7        Deque<int[]> candidates = new ArrayDeque<>();
8      
9        // Iterate over all points.
10        for (int[] point : points) {
11            int x = point[0];
12            int y = point[1];
13          
14            // Remove points from the start of the deque if their x values are out of the acceptable range (> k).
15            while (!candidates.isEmpty() && x - candidates.peekFirst()[0] > k) {
16                candidates.pollFirst();
17            }
18          
19            // If the deque is not empty, compute the potential answer using the current point 
20            // and the front of the deque, then update the answer if necessary.
21            if (!candidates.isEmpty()) {
22                answer = Math.max(answer, x + y + candidates.peekFirst()[1] - candidates.peekFirst()[0]);
23            }
24          
25            // Remove points from the end of the deque if they are no longer preferable.
26            // If the current point has a better y - x value, then it is a better candidate.
27            while (!candidates.isEmpty() && y - x >= candidates.peekLast()[1] - candidates.peekLast()[0]) {
28                candidates.pollLast();
29            }
30          
31            // Add the current point to the deque as it may be a candidate for future points.
32            candidates.offerLast(point);
33        }
34      
35        // Return the final computed answer.
36        return answer;
37    }
38}
39
1#include <vector>
2#include <deque>
3using std::vector;
4using std::deque;
5using std::pair;
6using std::max;
7
8class Solution {
9public:
10    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
11        int maxValue = INT_MIN; // Initialize maximum value to the smallest integer
12        deque<pair<int, int>> window; // Deque to maintain the sliding window of valid points
13
14        for (auto& point : points) {
15            int x = point[0], y = point[1];
16          
17            // Remove points from the front of the deque that are out of the current x's range (distance greater than k)
18            while (!window.empty() && x - window.front().first > k) {
19                window.pop_front();
20            }
21
22            // If the deque is not empty, calculate the potential maximum value using the front element
23            if (!window.empty()) {
24                maxValue = max(maxValue, x + y + window.front().second - window.front().first);
25            }
26
27            // Maintain a monotone decrease in the value of y - x by popping from the back of the deque
28            while (!window.empty() && y - x >= window.back().second - window.back().first) {
29                window.pop_back();
30            }
31
32            // Add the current point to the deque
33            window.emplace_back(x, y);
34        }
35
36        return maxValue; // Return the computed maximum value
37    }
38};
39
1function findMaxValueOfEquation(points: number[][], k: number): number {
2    // Initialize the answer to a very small number to start comparisons.
3    let maxValue = Number.MIN_SAFE_INTEGER;
4  
5    // Queue to maintain the points within the sliding window constraint.
6    const monoQueue: number[][] = [];
7  
8    for (const [xCurrent, yCurrent] of points) {
9        // Remove points from the queue that are outside the sliding window of 'k'.
10        while (monoQueue.length > 0 && xCurrent - monoQueue[0][0] > k) {
11            monoQueue.shift();
12        }
13      
14        // If the queue is not empty, calculate the potential answer.
15        if (monoQueue.length > 0) {
16            maxValue = Math.max(maxValue, xCurrent + yCurrent + monoQueue[0][1] - monoQueue[0][0]);
17        }
18      
19        // Maintain the elements in the monoQueue so that their y - x value is in decreasing order.
20        while (monoQueue.length > 0 && yCurrent - xCurrent > monoQueue[monoQueue.length - 1][1] - monoQueue[monoQueue.length - 1][0]) {
21            monoQueue.pop();
22        }
23      
24        // Add the current point to the queue.
25        monoQueue.push([xCurrent, yCurrent]);
26    }
27  
28    // Return the maximum value from all calculated values.
29    return maxValue;
30}
31
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

The given code snippet finds the maximum value of the equation |xi - xj| + yi + yj specified by the problem statement, with the constraint that |xi - xj| <= k for a list of point coordinates. The solution uses a deque to maintain a list of points that are within the distance k of the current point being considered.

Time Complexity:

  • The outer for loop goes through each of the n points once, so it has a time complexity of O(n).
  • The while loop inside the for loop pops elements from the front of the deque until the condition x - q[0][0] > k is not met. Each element is added to the deque at most once and removed from the deque at most once. Therefore, even though it looks like a nested loop, the total number of operations this loop will perform over the entire course of the algorithm is at most n, hence it contributes to an O(n) complexity.
  • The second while loop within the for loop is similar, as it also deals with each dequeued element at most once over the entire course of the algorithm. Thus, it too contributes to an O(n) complexity.

Since all of the operations are linear and the loops are working on disjoint operations (you do not have an O(n) operation for every other O(n) operation), these complexities add up in a linear fashion. Therefore, the overall time complexity of the algorithm is O(n).

Space Complexity:

  • The deque q stores at most n points at any given time, where n is the number of points, in the worst case scenario when all points are within the distance k from each other.
  • No other data structures or significant variables are used that scale with n.

The space occupied by the deque is the dominant factor, which gives us an overall space complexity of O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ