Problem

Submissions

Hints & solutions

Discuss

Maximum Value Of Equation

Moderate

0/80

Average time to solve is 15m

Contributed by

9 upvotes

Asked in companies

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

7 
0

Explanation of Sample Input 1 :

For the first test case, there are two pair of points (0, 1) and (2, 3) (Using 0 based indexing) which satisfy the given constraint |xi - xj| <= 'K'. The value of the equation for the first pair of points is 3 + 1 + |1 - 2| = 5. Similarly, the value of the equation for the second pair of points is 4 + 2 + |5 - 6| = 7. The maximum value is obtained by the second pair, and that is 7.

For the second test case, there is only one pair of point possible i.e. (0, 1). The value of equation for this pair is -5 + 5 + |3 - 3| = 0.

Sample Input 2 :

Sample Output 2 :

13
5

Explanation of Sample Input 2 :

For the first test case, the maximum value of the equation is obtained by (0, 1). And the value is 5 + 7 + |1 - 2| = 13.
For the second test case, the maximum value of the equation is obtained by (1, 3). And the value is -4 + 9 + |4 - 4| = 5.

Hint 1

Hint 2

Hint 3

Can you think of considering all possible pairs of points?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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.

Time Complexity

O(N^2), where N is the length of the given array/list.

Since we are iterating through every possible pair of elements in the given array/list using a nested loop. So the overall time complexity will be O(N^2).

Space Complexity

O(1)

Since we are not using any extra space. So the overall space complexity is O(1).

(100% EXP penalty)

Maximum Value Of Equation

Console