NINJA’S PLAN

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Facebook

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
7
4 2 3 1 3 1 2
5
5 4 3 2 1

Sample Output 1 :

0 4 6
0 1 2 3 4

Explanation of Sample Input 1 :

Test Case 1:

For the first test case given ‘HEIGHT_ARR’ is { 4, 2, 3, 1, 3, 1, 2 } so we return { 0, 4, 6 } 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. We have ‘3’ at the ‘2nd’ index and which is equal to ‘3’ at the ‘4th’ index so we include ‘3’ of the '4th' index and then ‘2’ at the last index.

Test Case 2:

For this test case given ‘HEIGHT_ARR’ is { 5, 4, 3, 2, 1 } so we return { 0, 1, 2, 3, 4 } as all the elements have smaller elements on the right side of the array.

Sample Input 2 :

2
3
5 10 20
5
6 7 3 2 1

Sample Output 2 :

2
1 2 3 4
Hint

Can you iterate the array?

Approaches (2)
Brute Approach

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

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

 

As for each element we are iterating the array.

Space Complexity

O(N), where ‘N’ is the size of the array.

 

As we are using an ‘ANS’ array for storing index.

Code Solution
(100% EXP penalty)
NINJA’S PLAN
Full screen
Console