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].
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
2
8
31 56 30 33 32 90 60 54
1
50
1 4 1 2 1 0 0 0
0
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.
2
5
90 80 70 60 50
5
50 60 70 80 90
0 0 0 0 0
1 1 1 1 0
Can you find the next increasing character by iterating through the array again?
For each puzzle, we iterate for the upcoming puzzles and check when we will get the puzzle with a higher difficulty level.
Algorithm
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).
O(1)
Constant space is used.
All tags
Sort by
Interview problems
Python O(n) solution using stack
def harderPuzzle(n, puzzle):
stack=[]
ans=[]
stack.append(n-1)
ans.append(0)
for i in range(n-2,-1,-1):
while len(stack)!=0 and puzzle[stack[-1]]<=puzzle[i]:
stack.pop()
if len(stack)==0:
ans.append(0)
else:
ans.append(stack[-1]-i)
stack.append(i)
return ans[::-1]
Interview problems
easy C++ solution
#include <bits/stdc++.h>
vector<int> harderPuzzle(int n, vector<int> &arr)
{
vector<int> ans(n, 0);
stack<int> st;
for(int i = n-1; i >= 0; i--){
if(st.empty()){
st.push(i);
}
else{
while(!st.empty() && arr[i] >= arr[st.top()]){
st.pop();
}
if(!st.empty()){
ans[i] = st.top() - i;
}
st.push(i);
}
}
return ans;
}Interview problems
C++
#include <bits/stdc++.h>
vector<int> harderPuzzle(int n, vector<int> &arr)
{
// Write your code here.
vector<int> ans(n , 0);
stack<int> st;
for(int i=n-1 ; i>=0 ; i--)
{
while(!st.empty() && arr[st.top()]<=arr[i])
st.pop();
if(!st.empty())
ans[i] = st.top() - i;
st.push(i);
}
return ans;
}Interview problems
Discussion thread on Interview Problem | Martha And Puzzles
Hey everyone, creating this thread to discuss the interview problem - Martha And Puzzles.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Martha And Puzzles
