Find The Nearest Supporter

Easy

0/40

Average time to solve is 10m

Contributed by

29 upvotes

Asked in company

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).

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1

2
5
3 1 5 12 10
6
9 8 1 2 5 5

Sample Output 1

-1 -1 1 5 5
-1 -1 -1 1 2 2

Explanation of Sample Input 1(1-based indexing)

Test Case 1:

There is no contestant on the left of 1st contestant
No contestant’s rating is less than this player, hence -1.
Both ratings 3 and 1 are smaller than the current rating, but ‘1’ is closest.
All ratings are small, but the nearest one is ‘5’.
For ‘10’, the nearest rating is ‘5’, as contestant 4 is not a supporter.

Test Case 2:

For the first '3' contestants, there is no supporter.
For contestant '4', the only supporter is contestant '3', with the rating '1'.
Both ratings '1' and '2' are smaller than the current rating, but ‘2’ is closest.
The rating of contestant '5' is not less than the current contestant, hence the closest supporter is 4th, with a rating of '2'.

Sample Input 2

Sample Output 2

-1 -1 -1 1 4
-1 1 2 3

Hint 1

Hint 2

Try checking all the contestants for each Position.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N*N), Where ‘N’ is the size of the row.

We are searching for all the left elements in the worst case, for each element.

Space Complexity

O(N), Where ‘N’ is the size of the row.

To store the outputs, we need to have a vector of minimum size ‘N’.

(100% EXP penalty)

Find The Nearest Supporter

Console