Last Updated: 12 Apr, 2021
NINJA’S PLAN
Moderate
Asked in company
Ninja has called a meeting of his team members for discussing how they can keep an eye on their enemies from their society. So they made a plan that they will choose such buildings in their locality from which they are capable of seeing the right side as they know the only entry point is on the right side.
As there are various types of buildings in the society of different heights, therefore, they made a plan to choose such buildings which have lower buildings in the right direction from them.
So your task is to help Ninja in finding the buildings which have lower height buildings on the right side.
Formally, return the index of those buildings which have lower height buildings on the right side. You will be provided an arrays/list ‘HEIGHT_ARR’, where ‘HEIGHT_ARR[i]’ represents the height of the ‘ith’ building.
Example :
Suppose given ‘HEIGHT_ARR’ is { 4, 2, 3, 1 } so we return { 0, 2, 3 } as ‘0th’ index building is ‘4’ which is greater than all other buildings on the right side. ‘1st’ index has ‘2’ which is smaller than ‘3’ so we don’t include it (hidden by building height with ‘3’). We include ‘3’ as it is greater than ‘1’ then we consider ‘1’ as nothing is on the right side of ‘1’.
Input Format :
The first line of input contains a ‘T’ number of test cases.
The first line of each test case contains an integer ‘N’ i.e size of the array ‘HEIGHT_ARR’.
The second line of each test case contains an array ‘HEIGHT_ARR’, where ‘HEIGHT_ARR[i]’ denotes the height of the ‘ith’ building.
Output Format :
For each test case, return an array containing the index of those building which have a smaller building in the right side of them.
Note :
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 100
1 <= N <= 1000
1 <= HEIGHT_ARR[i] <= 10^5
Where ‘T’ represents the number of test cases and ‘N’ represents the size of the array and ‘HEIGHT_ARR[i]’ represents the elements of the array.
Time Limit: 1 second
Approaches
The idea here is to traverse the array starting from the ‘0th’ index and look for the given condition.
- Firstly we declare a variable of type bool ‘flag’ and initialize it with ‘true’ and an array ‘ANS’ for storing the index of possible buildings.
- Now we start iterating our array and for each element, we traverse the right side of the array starting from that element
- If we encounter such an element that has a value greater than the current element we make the flag false and break the loop.
- Else we traverse the whole loop.
- Now we check:
- If our flag is true we insert the index into the ‘ANS’ array
- Else we continue the main loop.
- At last, we simply return the ‘ans’ array.
The idea here is to traverse the array from last and maintain a maximum and if the element is greater than the maximum we choose that element.
- Firstly we declare a variable named ‘max’ for storing maximum value and initialize it with ‘0’ and an array ‘ANS’ for storing index.
- Now we start traversing the array from the last index and for each index we check
- If it is greater than ‘max’ we store that index into our array and update the maximum if the current index element is greater than ‘max’
- Else we go on traversing.
- Now after the loop as we know our index is in reverse order so we return our ‘ANS’ array after reversing.