Last Updated: 26 Apr, 2021

Martha And Puzzles

Moderate
Asked in companies
BarclaysSalesforceBNY Mellon

Problem statement

Martha is a very bright student. She loves solving high-level puzzles. She has a list of ‘N’ puzzles. Each puzzle has some difficulty level. There is a rule that one can only solve a puzzle with difficulty ‘X’ if she has already solved all the puzzles with difficulty less than ‘X’. She can’t wait to get a puzzle having a difficulty level higher than the current puzzle.

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

02 Approach

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

 

  • Declare an array ‘ANS’ of size ‘N’ to store the answer. This will contain elements of type int and initially, it contains all zeros as elements
  • If ‘N’ is less than or equal to 1 then return ‘ANS’, because in such case there will be no puzzle having a higher difficulty level.
  • Declare a stack named ‘HARDER’ to store the index of the difficult level puzzles.
  • Iterate form ‘N-1’ till 0. (let the iterator be ‘i’)
    • While( ‘HARDER' is not empty and ‘PUZZLE[i]’ >= ‘PUZZLE[HARDER.top()]’ ):
      • If ‘HARDER’ is empty then update ‘ANS’ as ‘ANS[i]’ = ‘HARDER’.top() - ‘i’.
    • Keep pushing index in the stack ‘HARDER’.push(i).
  • Return ‘ANS’.