Last Updated: 13 Dec, 2020
Maximum Value Of Equation
Moderate
Asked in companies
Given an array/list of integers, “POINTS” containing coordinates ('x', 'y') of ‘N’ points in 2D plane, sorted by x-values in non-decreasing order. You are supposed to find the maximum value of the equation ('yi + yj + |xi - xj|') where |'xi - xj'| <= ‘K’ and 0 <= 'i' < 'j' <= ‘N’ - 1.
Note:
It is guaranteed that there exists at least one pair of points in the given array/list that satisfies the constraint |'xi - xj'| <= 'K'.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains two integers separated by single space ‘N’ and ‘K’, where ‘N’ denotes the number of points in the array/list and the number ‘K’ described in the constraint of the above equation.
The next ‘N’ line contains two integers separated by space which denotes the coordinates of the points in the given array/list.
Output Format :
For each test case, print a single line that contains an integer denoting the maximum value of the given equation.
Note :
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= 'T' <= 50
2 <= 'N' <= 10^4
-10^4 <= 'xi, yi' <= 10^4
0 <= 'K' <= 10^4
Where (xi, yi) denotes the coordinates of i-th point of the given array/list.
Time Limit: 1 sec
Approaches
The basic idea of this approach is to consider all the possible pairs of points in the given array/list and check for the maximum value of the equation.
STEPS:
- Initialize a variable maxValue to INT_MIN which stores the maximum value of the equation.
- Start traversing the array/list using index i which denotes the first point such that 0 <= i <= N - 1.
- Create a nested loop and iterate through the array/list using index j which denotes the second point in the pair such that 0 <= i < j <= N - 1
- Now, for each pair of points denoted by (i, j) calculate the value of the equation and update the maxValue accordingly.
The basic idea of this approach is to use a sliding window technique to solve this task.
Let’s define a window as a subarray (i, j) of the given array/list where i and j denote the left and right end of the window such that |xi - xj| <= K.
Now we are looking for a pair of points that maximizes the value of the function yi + yj + |xi - xj|. Observe that, for j > i, we can rewrite this function as yi + yj +xj - xi because the array/list is sorted by x-values in non-decreasing order (It has been given in the problem description).
Now note that the value (xj + yj) is fixed if we are at jth index. So the task breaks down into finding the maximum value of (yi - xi) such that i < j. We can easily solve this problem using the max-heap to store such values so that we can efficiently get the maximum value.
STEPS :
- Initialize a max-heap which stores the pair <yi - xi, xi>, where (xi, yi) denotes the coordinates of the i-th point in the array/list. And also initialise a variable maxValue to INT_MIN which stores the maximum value of the function.
- Now, start traversing in the given array/list from start to end using an index j which also denotes the second point.
- Remove all the elements from the top of the heap for which |xi - xj| <= K doesn’t hold and increment the value of i.
- Get the top element from the heap, which is the maximum value in the current window, and update the maxValue accordingly.
- Push <yj - xj, xj> i.e. the current point in the heap and increment the value of j.
- Print the maxValue which is the maximum value of the function.
We need to find the maximum value of (yj + yi + | xi - xj |) . Since it is given in the problem description that the points array/list are sorted in non-decreasing order by x-values which means we can write the equation as yi - xi + (xj + yj) for i < j.
Now note that the value (xj + yj) is fixed if we are at the jth index. So the task breaks down into finding the maximum value of yi - xi such that i < j. We can easily solve this problem using a deque. This problem is a slight modification of the Sliding Window Maximum problem.
The idea here is to use the sliding window technique and to maintain a non-increasing deque for the window such that the front element denotes the index of point for which (yi - xi) is maximum.
STEPS:
- Initialize a deque window that stores the index of the point in the given array/list. Also, initialize a variable maxValue to a large negative number to store the maximum value of the equation.
- Start traversing the array from the front using a variable j which denotes the current point such that 0 <= j <= N - 1.
- Now, remove all the elements from the front of the window for which |xi - xj| <= K doesn’t hold.
- Get the front element of the window, which is the index of the point for which (yi - xi) is maximum in the current window, and update the “maxValue” accordingly.
- Now, remove all the elements from the back of the window for which the value (yi - xi) is smaller than (yj - xj) because we want to maintain a non-increasing deque.
- Insert the index of the current point at the end of the window.
- Print the maxValue which is the maximum value of the function.
Similar problems