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:
list, to avoid the "contiguous memory block" problem that lists may encounter.
appendare both O(1), the heaviest operation is the
inc(especially so if
iis large). So I keep all items as integers to avoid conversion from string to int multiple times in the