Ninja’s Test

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
MathworksFlipkart limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4
1 2 3 1
3
3 4 1
Sample Output 1:
 1
 2
Explanation:
For the first test case, the difference between the nearest left and the right smaller element of ‘ARR[2],’ i.e., 2 - 1 = 1 is maximum possible. Hence the answer is 1.

For the second test case, the difference between the nearest left and the right smaller element of ‘ARR[1],’ i.e., 3 - 1 = 2, is maximum possible. Hence the answer is 2.
Sample Input 2:
2
4
1 2 3 4
3
1 1 1
Sample Output 2:
3
0
Hint

Find nearest left and right for every element.

Approaches (2)
Brute Force

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

O(N ^ 2), where N is the size of the ‘ARR’.
 

For every element, we will be checking nearly every other element in the array. Hence the overall time complexity is O(N ^ 2).

Space Complexity

O(N).
 

The size of arrays, ‘LEFTSMALLER’ and ‘RIGHTSMALLER’ will be ‘N’. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja’s Test
Full screen
Console