Last Updated: 9 Jan, 2021

Find The Nearest Supporter

Easy

Asked in company

Solve now

Problem statement

There are contestants standing in a row. Each contestant is assigned a rating, which is an integer. A contestant supports all those whose rating is greater than their rating.

Now for each contestant standing in the row, you need to tell the rating of its closest supporter on the left.

If no supporter is there, store -1 in that place.

For Example

Consider the row : [ 3, 1, 5, 12, 10], with 1-based indexing -
For index 3, there would be 2 supporters, index 1 and index 2, but index 2 is closest, hence for index 3, we will store ‘1’ (Rating of contestant). 
For index 5, we will store ‘5’(at index 3).

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’, which represents the size of the row.

The second line for each test case ‘N’ space-separated integers denoting the corresponding elements of the row.

Output Format

For each test case, you need to print space-separated integers denoting the rating of the closest supporter on the left.

Print the output of each test case in a separated line.

Note

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 50
1 <= N <= 10000
-10^9 <= data <= 10^9

Where ‘data’ represents the given row elements.

Time limit: 1 sec

Solve now

Approaches

01 Approach

For each contestant, check all the players on the left side until one with a rating less than its rating is found.

For each index in the given array:-
- Choose the starting position as ‘index-1’.
- Check if the rating of a player is less than the current contestant or not.
- If less put/update this value in the output array/list for the current ‘index’.
- Else reduce the position by 1.
- If no position is found, put -1 in the output array/list for this position.
Return from the function.

Solve now

02 Approach

What we can observe is that, if we encounter a value, then we can remove all the values which are processed and are greater than this value, as in the future they can’t be the answer for any contestant(as we already have a smaller rating which is near).

Create an empty stack ‘s’.
For each index:-
- Let the current rating is ‘x’.
- Keep removing all the elements from the top of the stack, which are greater than or equal to ‘x’.
- If ‘s’ is empty, put -1 in the output, as no value is smaller than ‘x’.
- Else the top of the stack is the required value.
- Push ‘x’ in stack ‘s’(for all next elements).
Return from the function.

Solve now