7
\$\begingroup\$

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

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

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(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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.