# Push, Delete and Print stack elements

I've tried asking about the performance on the HackerRank discussion forum, it didn't work out.

The task is to write a program with three operations:

 1 x  Push the element x onto the stack.
2    Delete the element present at the top of the stack.
3    Print the maximum element in the stack.


The first input line is the number of lines in the program, all subsequent lines are one of the three instructions.

Sample Input:

 10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3


Sample Output:

 26
91


My Solution:

data = []
for _ in range(int(input())):
ins = input().split()
if ins[0] == '1':
data.append(int(ins[1]))
elif ins[0] == '2':
data.pop()
else:
print(max(data))


It gets slow on working with input size of 1000 elements or so, how could I speed this up?

• You should keep track of the maximum, because using max(data) needs to go through the whole list. Sep 16, 2016 at 10:09
• You should also think of a better title. A title that describes what your code does and not what you want out of a review attracts a lot more views and consequentially also more answers. Sep 16, 2016 at 10:47
• @Graipher Thanks for that It looks much better now Sep 16, 2016 at 10:59

Try tracking the current maximum, otherwise frequent occurrences of 3 will push your run time towards $\mathcal{O}(n^2)$.

If you take a closer look at what your input actually means, you will notice that smaller values being pushed onto the stack have actually no significance if a greater value has being pushed previously. So for every fill level of the stack, you already know the corresponding maximum at the time you push onto the stack.

Use that knowledge:

current_max = []
for _ in range(int(input())):
ins = input().split()
if ins[0] == '1':
new_max = int(ins[1])
if current_max and new_max < current_max[-1]:
new_max = current_max[-1]
current_max.append(new_max)
elif ins[0] == '2':
current_max.pop()
elif ins[0] == '3':
print(current_max[-1])


By storing the maximum instead of the raw value on the stack, you can always access the current maximum directly. Just don't forget to handle the special case when data is empty, so the new value will always be the maximum.

• I agree, the max is probably what is killing the time for large lists. However, there should also be a handling in the pop part, because you might pop off the maximum value. Sep 16, 2016 at 11:05
• No popping the max value is allowed please see the sample input and sample out @Graipher Sep 16, 2016 at 11:07
• @JøêGrèéñ Well, this is something you should explicitly state! Just because it does not happen in your one example does not mean it is not going to happen. The defined instructions would allow for it (and do not say what happens if you try to pop the maximum value). Sep 16, 2016 at 11:08
• @Graipher Even when the former maximum is popped - the top of data still holds the next valid maximum, which is always <= the former maximum. Sep 16, 2016 at 11:33
• @JøêGrèéñ The size of the stack needs to correspond with the number of push operations specified by the input. If the data is smaller than the current maximum, you still need to push something onto the stack. The safest value for that is simply copying the current maximum instead, since the data you just received can never be maximum anyway. Sep 16, 2016 at 11:37

One remark. A stack is not a set, you could have the maximal value happening twice. And deletes may happen too.

This in fact means you need a running maximum.

Hence create a stack of a pair (value, max till now).

The implementation then is quite simple for all three operations.......

• I havn't used a set sir Sep 16, 2016 at 11:02
• I meant a mathematical set, where all values are unique. The first answer is fine, but ticklish. Because deleting a prior max value can find the same max value if that value was pushed twice. Hence my proposal. Sep 16, 2016 at 11:08
• @JoeWallis it was intended as a warning that a stack can have several max values. So deleting a max value does not automatically give a smaller max value, and adding the same max value needs needs to duplicate that max value. Must express myself more clear, thanks. Sep 16, 2016 at 11:25
• The actual value is completely irrelevant for this problem. Just recording "max till now" is completely sufficient. Which is exactly what the accepted answer does. Sep 16, 2016 at 11:31
• @JoopEggen I failed to understand the bolded part of your answer as I was fixated on the set part. I noticed after posting my comment and so deleted it, in the hopes you'd not have seen it. Your reasoning is definitely clear in your comment. Sep 16, 2016 at 11:31