Optimizing Efficiency in a Stack

Question

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

Answer 1

Just be lazy. Don't do what you're told. They'll never know.

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.

Now all three operations are O(1).

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(i²). 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.