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].
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.
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.
You don’t need to print anything; It has already been taken care of.
1 <= ‘T’ <= 50
1 <= ‘N’ <= 10^4
30 <= ‘PUZZLE[i]’ <= 100
Where, 'PUZZLE[i]' represents the difficulty level of puzzle 'i'.
Time limit: 1sec
For each puzzle, we iterate for the upcoming puzzles and check when we will get the puzzle with a higher difficulty level.
Algorithm
For each index, the index of the next greater element is to be found. By maintaining a stack and popping all the elements which are smaller than the current number, we can get the next greater for each index.
Algorithm
Postorder Traversal
Postorder Traversal
Min Stack
Min Stack
Min Stack
Min Stack
Min Stack
Min Stack
Min Stack
Min Stack
Stock Span
Stock Span
Hills and Soldier
Hills and Soldier
Hills and Soldier
Hills and Soldier
Hills and Soldier
Next Greater Element II