Martha And Puzzles

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
8
31 56 30 33 32 90 60 54
1
50
Sample Output 1 :
1 4 1 2 1 0 0 0
0
Explanation For Sample Input 1 :
The first test case for 31 next increasing difficulty = 56 (index diff = 1).
For 56 next increasing difficulty = 90 (index diff = 4).
Similarly, check for 30,33, and 32.
For, 90,60, and 54 there are no greater elements. 

In the second test case, there is only one puzzle, so the answer will be zero.
Sample Input 2 :
2
5
90 80 70 60 50
5
50 60 70 80 90
Sample Output 2 :
0 0 0 0 0 
1 1 1 1 0
Hint

Can you find the next increasing character by iterating through the array again?

Approaches (2)
Brute Force 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’.
Time Complexity

O(N^2), where ‘N’ is the size of the ‘PUZZLE’ array.
 

For each puzzle, we iterate for the upcoming puzzles. So the time complexity will be O(N^2).

Space Complexity

O(1)

 

Constant space is used.

Code Solution
(100% EXP penalty)
Martha And Puzzles
Full screen
Console