Last Updated: 26 Apr, 2021

# Martha And Puzzles

Moderate

## Problem statement

#### Your task is to tell Martha how long she has to wait to get a puzzle having a higher difficulty level than the current puzzle. If there is no puzzle ahead with a higher difficulty level, just print "0".

##### For Example :
``````Let â€˜Nâ€™ = 5 and â€˜PUZZLEâ€™ = [ 30, 40, 80, 50, 70 ]

After solving the first puzzle, the very next puzzle has a difficulty level 40 and 40 > 30.
Then after 40, the very next puzzle has a difficulty level 80 and 80 > 40.
But for 80, there is no puzzle having a difficulty level greater than 80.
For 50, the very next puzzle has a difficulty level 70 and 70 > 50.
Again for 70, there is no puzzle having a difficulty level greater than 70.

So the output will be [1, 1, 0, 1, 0].
``````
##### Input Format :
``````The first line contains a single integer â€˜Tâ€™ representing the number of test cases.

The first line of each test case contains an integer â€˜Nâ€™ representing the number of puzzles.

The second line contains â€˜Nâ€™ space-separated integers representing the difficulty level of these â€˜N' puzzles.
``````
##### Output Format :
``````For each test case, return a list of size â€˜Nâ€™ representing the wait Martha has to do after each puzzle to get a puzzle of higher difficulty level.

Output for every test case will be printed in a separate line.
``````
##### Note :
``````You donâ€™t need to print anything; It has already been taken care of.
``````
##### Constraints :
``````1 <= â€˜Tâ€™ <= 50
1 <= â€˜Nâ€™ <= 10^4
30 <= â€˜PUZZLE[i]â€™ <= 100
Where, 'PUZZLE[i]' represents the difficulty level of puzzle 'i'.

Time limit: 1sec
``````

## Approaches

### 01 Approach

For each puzzle, we iterate for the upcoming puzzles and check when we will get the puzzle with a higher difficulty level.

Algorithm

• Initialize an array â€˜ANSâ€™ to store the answer. This will be of type int.
• Iterate from 0 to â€˜Nâ€™. (let the iterator be â€˜iâ€™):
• Initialize a variable â€˜COUNT = 0â€™ to maintain the counter of each passing value. It will be of type int.
• Initialize a variable â€˜FLAG = falseâ€™ to check if a higher value is found or not. It will be of type boolean.
• Iterate from â€˜i+1â€™ to â€˜Nâ€™. (let the iterator be â€˜jâ€™):
• Increase â€˜COUNTâ€™ every time by 1.
• If â€˜PUZZLE[j]â€™ > â€˜PUZZLE[i]â€™ then change â€˜FLAGâ€™ to true, and break this loop.
• If â€˜FLAGâ€™ = true then add â€˜COUNTâ€™ to â€˜ANS[i]â€™
• Else if â€˜FLAGâ€™ = false then â€˜ANS[i]â€™ = 0 as there is no higher value.
• Return â€˜ANSâ€™.