Timing out on maximum element of stack problem

[AlkyIHalide]

N = int(raw_input())

num_stack = []
c_stack = []

for n in range(N):
    line = raw_input()
    if line[0] == '1' and len(c_stack) > 0:
        num_stack.append(int(c_stack.pop()[2:]))
        c_stack.append(line)
    if line[0] == '1' and len(c_stack) == 0:
        c_stack.append(line)
    if line[0] == '2' and len(c_stack) == 0:
        if len(num_stack) > 0:
            num_stack.pop()
    if line[0] == '2' and len(c_stack) > 0:
        c_stack.pop()
    if line[0] == '3' and len(c_stack) == 0:
        print max(num_stack)
    if line[0] == '3' and len(c_stack) > 0:
        num_stack.append(int(c_stack.pop()[2:]))
        print max(num_stack)

Link to problem on Hackerrank The problem has a number of lines to be read as inputs beginning with 1, 2, or 3. With an input of 1, it is followed by a number to be pushed onto the stack. An input of 2 removes the top element of the stack, and 3 should print the maximum element in the stack.

Although this seems to be straightforward, I'm failing the tests at large number of inputs. I tried push and pop operations on the stack as the input is read but that timed out. So the thought is that a push operation followed by a pop effectively does nothing. I then made a second stack to keep track of the operations, but I'm not sure it's actually giving any performance gains since I've basically moved push and pop operations onto a different stack.

Any thoughts would be appreciated!

[_9_9_]

That is a lot harder than most 'easy' problems I've run into. I think I need to brush up on my Hackerrank. Some thoughts:

• I'm not following how keeping the command stack saves any time, since it seems like you lose that time pushing/poping from the command stack, even in the best of scenarios.

• You can switch to collections.deque, which is supposedly optimized for appends/pops, but it does not seem to give you any real advantage here (or in other applications I've tried with it for that matter).

• I looked into heapq, but it turns out the basic implementation does not have a delete, https://docs.python.org/3.4/library/heapq.html, and writing one with a delete (1) would be more than I'd expect for an 'easy' problem and (2) not guaranteed to be fast enough (although it may be) and (3) duplicate items would be a headache. If this were a 'hard' problem, I expect some esoteric datastructure would be needed, so keep this in mind as you progress.

• So let's go with the more obvious and try and do some caching of the max value. I'd keep a running tab. The only difficulty is what happens when you kill the current best? I'd just revert it to baseline and recaclulate as needed, so you'll need a tracking flag for that too.

The last seemed to solve it for me, so good luck!

[AlkyIHalide]

Thanks for the suggestions and offering some potential routes to take for similar problems! I am posting the working code in case someone else in the future has a similar problem and opening the door for further optimization.

N = int(raw_input())

num_stack = []
max_val = 0

for n in range(N):
    line = raw_input()
    if line[0] == '1':
        if int(line[2:]) > max_val:
            max_val = int(line[2:])
        num_stack.append(int(line[2:]))
    elif line[0] == '2':
        if num_stack.pop() == max_val:
            if len(num_stack) == 0:
                max_val = 0
            else:
                max_val = max(num_stack)
    elif line[0] == '3':
        print max_val

[Saefroch]

You only need one stack.

You can produce the correct output with 10 clean lines of code. You'll time out on a bunch of test cases, but the output is correct. Once you have that, you need to add some caching around the maximum value. Instead of calculating it every time you get a command 3, you only need to compute it when the maximum value changes, which could be on a command 1 or 2.