Push, Delete and Print stack elements

Question

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?

Answer 1

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.

Answer 2

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