Last Updated: 5 Sep, 2021
Difference Between Indices
Hard
Asked in company
You are given an array ‘arr’ of size ‘N’. You have to find two indices, ‘i’ and ‘j’, such that arr[j] > arr[i] and the difference between ‘j’ and ‘i’ is maximized. If there are no two indices such that arr[j] > arr[i] then return -1.
For example:
Consider arr =[1, 2, 3, 4, 5], we can take indices i = 0, and j = 4, so difference is 4 - 0 = 4, and arr[4] > arr[0]. Hence the answer is 4.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the size of the array ‘arr’.
The second line of each test case contains ‘N’ space-separated integers representing the elements of the array ‘arr’.
Output Format:
For each test case, print a single integer representing the maximum difference between ‘j’ and ‘i’ such that arr[j] > arr[i].
The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 6
1<= arr[i] <= 10 ^ 9
Time limit: 1 sec
Approaches
We will run two for loops to check whether there exist two indices, such that the difference of indexes is maximized and arr[j] > arr[i].
Algorithm:
- Run a for loop from index ‘i’ = 0 to n - 1
- Run another for loop from index ‘j’ = i + 1 to n - 1
- Check if arr[j] > arr[i] :
- If yes, then update maximum answer.
- Otherwise, do not update.
- Check if arr[j] > arr[i] :
- Run another for loop from index ‘j’ = i + 1 to n - 1
We will sort the array and maintain the order of indexes. After sorting the array ‘arr’, we know that the elements are in increasing order. So all we need to do is maximize the difference between the indexes. For every index, we need to check for the highest index present ahead. We can do this in constant time if we maintain a suffix array that provides us the information of the maximum index.
Algorithm:
- Save the indexes of elements of array ‘arr’.
- Sort the array ‘arr’
- Maintain a suffix array, in which the element at each index indicates the maximum number of indexes ahead.
- Run a for loop from i = ‘0’ to ‘N’:
- For each ‘i’, check the maximum index present ahead with the help of the suffix array, and then update the difference between that maximum index and index of the current element.
- Return the final updated answer.
All we need to do is maintain two pointers left and right, such that arr[right] > arr[left] and right-left are maximum.
Now, if we try to fix the left pointer for any element ‘E’, we will check if there is an element less in value behind this element ‘E’. If yes, then we will fix the left pointer there. Similarly, if we try to fix the right pointer for any element ‘E’, we will check if there exists an element higher in value in front of this element ‘E’. If yes, then we will fix the right pointer there.
In order to check for the higher element in front, we can maintain a maximum DP-suffix array which can get us the maximum element in constant time. Also, in order to check for the lesser element from the left, we can maintain a minimum DP-prefix array.
Algorithm:
- Maintain a DP-prefix array ‘prefix’, which stores the current minimum element from the beginning
- In order to maintain minimum prefix array, run a loop from ‘i’ = 0 to ‘N’-1
- Store the current minimum value in a variable.
- Add the current minimum value in the prefix array.
- Maintain a DP-Suffix array ‘suffix’, which stores the current maximum element from the end.
- In order to maintain maximum suffix array, run a loop from ‘i’ = ‘N’-1 to ‘0’
- Store the current maximum value in a variable.
- Add the current maximum value in the suffix array.
- All we now need to do is to find the maximum difference we can achieve.
- Maintain two pointers ‘left’ = 0 pointing to ‘prefix’ and ‘right’ = 0 pointing to ‘suffix’.
- While ‘left’ < size of prefix and ‘right’ < size of suffix
- While prefix[left] <= suffix[right]
- Keep Incrementing ‘right’ by 1.
- Now, as soon as we break from the loop
- Increment the value of ‘left’ by 1.
- While prefix[left] <= suffix[right]
- Update the maximum ‘answer’ to ‘right’-’left’, if the previous answer is less than ‘right’-’left’.
- Finally, return the ‘answer’.