Last Updated: 13 Mar, 2021
Maximum Difference in Positions
Moderate
Asked in companies
There are ‘N’ students sitting in a row each having some marks that they have obtained in the previous examinations. You have to find the maximum difference in the position of two students such that the second student has marks greater or equal to the first student. Formerly, You have to find the maximum value of ‘j’ - ‘i’ such that ‘i’ < ‘j’ and arr[ i ] <= arr[ j ].
Note:
Return 0, if there are no such two students present.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a single integer ‘N’ which denotes the number of students in the row.
The second line of each test case contains the ‘N’ space-separated integers in which the “i-th” number represents the marks of the “i-th” student.
Output Format:
For each test case, print the maximum difference between the two students described above. If, there are no such students then print 0.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 50
2 <= N <= 10000
0 <= arr[ i ] <= 10^5
Where ‘T’ is the number of test cases.
Where 'N' is the number of students in the row and “arr[ i ]” denotes the marks of “i-th” student.
Time limit: 1 sec
Approaches
The basic idea is to iterate through all the pairs of students and find the maximum difference between two students such that the first one has marks less than or equal to the second one.
The steps are as follows:
- Create a variable to store the answer. (say, “ans”)
- Iterate through the “arr”. (say, iterator = ‘i’)
- Iterate again through the “arr” but from ‘i’ + 1. (say, iterator = ‘j’)
- Check if arr[ i ] is less than or equal to arr[ j ] then store the maximum between the “ans” and ‘j’ - ‘i’ in the “ans”.
- Iterate again through the “arr” but from ‘i’ + 1. (say, iterator = ‘j’)
- Return “ans”.
The basic idea of this approach is to sort the given arrays according to the marks of the students in decreasing order. Now, if we traverse this new array from last to start then there is always arr[ i ] >= arr[ i + 1] and so, all we have to do is to find the maximum difference between the indexes of these students.
The steps are as follows:
- Create an extra vector of pairs named ‘v’ and store the elements of the given array along with their indexes.
- Sort ‘v’ such that marks/first value of the pair will be in decreasing order.
- Create two variables (“ans” and “mini”) to store the answer and minimum index/second value of the pair, respectively.
- Initialize “ans” with 0 and “mini” with v[ ‘N’ - 1].second.
- Iterate through ‘v’ from ‘N’ - 2 to 0. (say, iterator = ‘i’)
- Check if the index stored at ‘i’ in ‘v’ is greater than “mini” then store their difference in the “ans”.
- Else, make “mini” equal to this index.
- Return “ans”.
The basic idea of this approach is to store the minimum and maximum element in the left and right of each element and for this, we will use the concept of prefix and suffix arrays.
For Example:
arr = [ 11, 4, 1, 5, 6, 7, 9, 8 ]
prefix = [ 11, 4, 1, 1, 1, 1, 1, 1 ]
suffix = [ 9, 9, 9, 9, 9, 9, 9, 8 ]
Here, “arr” is the given array, “prefix” is an array that holds the minimum value at every index while moving from left to right in the “arr”, and “suffix” is an array that holds the maximum value at every index while moving from right to left in the “arr”.
We start from ‘i’ = 0 and ‘j’ = 0 where ‘i’ is the iterator on prefix and ‘j’ is on the suffix. We increment ‘i’ by 1 because 11 is not less than or equal to 9. Now, ‘i’ becomes 1 and ‘j’ is still at 0. After this, we will keep incrementing the ‘j’ until the value corresponding to ‘j’ becomes less than or equal to the value corresponding to ‘i’ or ‘j’ reaches the end.
In the above example, ‘j’ will reach the end because the value corresponds to ‘i’ is 4 which is less than 8.
All we are trying to do is to always maintain property arr[ i ] <= arr[ j ] and find the maximum possible difference between the indexes.
The steps are as follows:
- Create two arrays/lists “prefix” and “suffix” to store the minimum element in the left and maximum element in the right, respectively.
- In “prefix” store the first element of “arr” initially and in “suffix” store the last element at the last index.
- Iterate through “arr” from index 1 and keep storing the minimum element in “prefix”.
- Iterate through “arr” from index ‘N’ - 2 to 0 and keep storing the maximum element in “suffix”.
- Create a variable “ans” to store the answer and initialize it with 0.
- Create two-pointer variables ‘i’ and ‘j’ which used to point the left minimum and right maximum. Initialize both of them with 0.
- Now, iterate till ‘i’ and ‘j’ both are less than ‘N’.
- If at any point the left minimum in “prefix” is less than the right maximum in “suffix” then store the maximum of “ans” and ‘j’ - ‘i’ in the “ans” and increment ‘j’ by 1.
- Else, just increment ‘i’ by 1.
- Return “ans”.