Optimizing Efficiency in a Stack

Question

I'm solving a problem on HackerRank where I'm required to implement a simple stack.

enter image description here

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:

  enter image description here

• 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

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

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.

• Rakesh Adhikesavan: How do you handle the case with multiple inc operations where the i value is lesser than previous inc operations. For example: ['push 1', 'push 2', 'push 3', 'inc 3 5', 'inc 1 5'] So the bottom-most element is now incremented by 10, while the top two are incremented by 5.
• superb rain: As described in the answer. There's nothing special about that.