# Optimizing Efficiency in a Stack

I'm solving a problem on HackerRank where I'm required to implement a simple stack. It's passing all the tests except for the last 4 where it fails due to surpassing the time constraint of 10s. These 4 failing tests are running 200,000 operations on the stack.

How can I optimize my code below:

# operations of the form ['push -36', 'pop', 'push 16', 'pop', 'inc 1 -17', ...]

from collections import deque

def superStack(operations):

def push(v):
S.append(int(v))

def pop():
return S.pop()

def inc(i,v):
i, v = int(i), int(v)
for pos in range(i):
S[pos] += v

S = deque()
funcs = locals()

for operation in operations:
op, *args = operation.split(' ')
funcs[op](*args)

print(S[-1] if S else "EMPTY")


A few notes:

• Some constraints: • I've chosen deque over list, to avoid the "contiguous memory block" problem that lists may encounter.

• Since pop and append are both O(1), the heaviest operation is the inc (especially so if i is large). So I keep all items as integers to avoid conversion from string to int multiple times in the inc loop

• Please link to the problem so we can try it ourselves. – superb rain Aug 8 '20 at 15:21
• @superbrain Unfortunately, I can't do that, I think it was part of a private test suite. And I no longer have access. – Jonathan Spiller Aug 8 '20 at 15:34

Instead of truly increasing the bottom i values right away, just make a note at the i-th value from the bottom to increase it by v when it gets popped. And when that pop happens, move the note to the value below, so it gets increased by v as well (when it gets popped). And so on, so that this will add v to all bottom i values (when they get popped).
To support multiple inc operations: If a value already has a note to add w to it (and all values below it), change that to w + v.
For easier coding, just store all values along with such a note, but with initial adding value 0.
Oh wait. Not quite O(1), since you're using a deque so you can't access an arbitrary index in O(1). That's actually a problem in your solution as well. Your increasing the bottom i values isn't O(i) but only O(i2). If you switch to a list, yours would be O(i) and mine would be O(1). This loses the O(1) of appending/popping to/from a deque, but the list still does them in amortized O(1). So then all three operations are amortized O(1). Alternatively you could keep your deque and store the notes in a separate dict, but then it's O(1) just as much as dict access is O(1) (i.e., not truly, but practically), and I suspect it would be a bit slower than the list version.