Last Updated: 28 Oct, 2021
Ninja’s Test
Moderate
Asked in companies
FAANG is the best coding school in Ninjaland. The Ninja wants to get admission into FAANG. To get admission into FAANG, Ninja needs to clear its admission test, which is as follows:
Given an integer array ‘ARR’ of size ‘N’, find the maximum absolute difference between the nearest left and the right smaller element of every element in ‘ARR’. If there is no left smaller or right smaller element of any element then take 0 as the smaller element.
Can you help Ninja to clear the admission test?
For example:
You are given ‘ARR’ = [1, 2, 3, 1]. The difference between the nearest left and the right smaller element of ‘ARR[2],’ i.e., 2 - 1 = 1 is the maximum possible. Hence the answer is 1.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains an integer, ‘N’, representing the size of the ‘ARR’.
The second line of each test case contains ‘N’ space-separated integers, representing the elements of ‘ARR’.
Output Format:
For each test case, print a single integer, denoting the maximum absolute difference between the nearest left and the right smaller element of every element in ‘ARR’.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 5000
1 <= ARR[i] <= 10^6
Time limit: 1 sec
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Approaches
In this approach, we will use two arrays, ‘LEFTSMALLER’ to store the nearest left smaller element for every element of ‘ARR’ and ‘the RIGHT SMALLER’ to store the nearest right smaller for every element in ‘ARR’. ‘LEFTSMALLER[I]’ will store the nearest left smaller element of the ith element of ‘ARR’. Similarly, ‘RIGHTSMALLER[I]’ will store the nearest right smaller element of the ith element of ‘ARR’.
Then, we update the maximum difference according to the difference of ‘LEFTSMALLER[I]’ and ‘RIGHTSMALLER[I]’.
To find the nearest right smaller element of any element, we will run a loop on its right side. As soon as we find an element on its right side that is smaller than it, we will break the loop, assign it as the nearest right smaller element of this element, move forward, and do the same for the next element.
Now, to find the nearest left smaller element of any element, we will reverse the ‘ARR’ and find the nearest right smaller element.
Algorithm:
- Initialize an integer array 'RIGHTSMALLER' of size 'N'.
- Call 'FINDRIGHTSMALLER' to find the right smaller element of every element.
- Initialize an integer array 'LEFTSMALLER' of size 'N'.
- Reverse the 'ARR' to use 'FINDRIGHTSMALLER' to find the left smaller element of every element.
- Call 'FINDRIGHTSMALLER' to find the left smaller element of every element.
- Initialize a variable 'ANS' to store the final answer.
- Iterate 'I' in 0 to 'N'
- Set 'ANS' to the maximum of 'ANS' and 'ABSOLUTE'('LEFTSMALLER[I]' - 'RIGHTSMALLER[I]').
- Finally, return 'ANS'.
Maintain a function ‘FINDRIGHTSMALLER’(‘N’, ‘ARR’, ‘RIGHTSMALLER’)
- Initialize a variable 'SMALL'.
- Iterate 'I' in 0 to 'N'
- Set 'SMALL' to 0.
- Iterate 'J' in 'I' + 1 to 'N.'
- If 'ARR[J]' is less than 'ARR[I]', set 'SMALL' to 'ARR[J]' and break.
- Set 'RIGHTSMALLER[I]' to 'SMALL'.
Maintain a function ‘REVERSE’(‘ARR’)
- Iterate 'I' in 0 to 'ARR.LENGTH/2':
- Set 'TMP' as 'ARR[I]'.
- Set 'ARR[I]' as 'ARR[ARR.LENGTH - 1 - i]'.
- Set 'ARR[ARR.LENGTH - 1 - i]' as 'TMP'.
This approach is the same as the previous, one but instead of using two loops to find the smaller element, we will use a stack, which will help us to reduce time complexity from quadratic to linear.
For every element, we will find the nearest left smaller element using a stack. We will iterate through ‘ARR’, and for every element, we will keep removing the top of the stack while it is greater than or equal to the current element. Once all the greater elements have been removed, we will check if the stack still has elements or not. If the stack still has elements, they all will be smaller than the current, and the top of the stack will be the nearest smaller element.
Algorithm:
- Initialize an integer array 'RIGHTSMALLER' of size 'N'.
- Call 'FINDRIGHTSMALLER' to find the right smaller element of every element.
- Initialize an integer array 'LEFTSMALLER' of size 'N'.
- Reverse the 'ARR' to use 'FINDRIGHTSMALLER' to find the left smaller element of every element.
- Call 'FINDRIGHTSMALLER' to find the left smaller element of every element.
- Initialize a variable 'ANS' to store the final answer.
- Iterate 'I' in 0 to 'N'
- Set 'ANS' to the maximum of 'ANS' and 'ABSOLUTE'('LEFTSMALLER[I]' - 'RIGHTSMALLER[I]').
- Finally, return 'ANS'.
Maintain a function ‘FINDLEFTSMALLER’(‘N’, ‘ARR’, ‘LEFTSMALLER’)
- Initialize an empty stack 'ST'.
- Iterate 'I' in 0 to 'N'
- Keep removing the top of the 'ST’ while it is greater than or equal to 'ARR[I]'.
- If 'ST' is not empty, the top is the left smaller element of the current element.
- Otherwise, there is no smaller left element of the current element.
- Push current element to ‘ST’.
Maintain a function ‘REVERSE’(‘ARR’)
- Iterate 'I' in 0 to 'ARR.LENGTH/2':
- Set 'TMP' as 'ARR[I]'.
- Set 'ARR[I]' as 'ARR[ARR.LENGTH - 1 - i]'.
- Set 'ARR[ARR.LENGTH - 1 - i]' as 'TMP'.