CODEWITHSUNDEEP
pythonstack
Jarwyd
Jarwyd

Reputation: 45

Stacks and optimization - example from hackerrank

I have a question concerning stacks in Python. I tried to solve a Maximum Element task in Hackerrank:

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

To solve it I wrote something like this:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def maxEl(self):
        return max(self.items)


s = Stack()   

for i in range(int(input())):
    n = input().split()

    if n[0] == '1':
        s.push(int(n[1]))
    elif n[0] == '2':
        s.pop()
    else:
        print(s.maxEl())

It works, but too slow apparently and I pass only 18 out of 28 testcases (because of timeout). I have found a similar solution, and it is fast enough, but I don't understand why:

class Stack:
    def __init__(self):
        self.arr = [0]
        self.max = [0]

    def push(self, data):
        self.arr.append(data)
        if self.max[-1] <= data:
            self.max.append(data)

    def pop(self):
        if self.arr[-1] == self.max[-1]:
            self.max.pop()
        self.arr.pop()


N = int(input())
s = Stack()

for _ in range(N):
    x = str(input())

    if x[0] == '1':
        s.push(int(x[2:]))

    elif x[0] == '2':
        s.pop()

    else:
        print(s.max[-1])

Can somebody explain me why my code isn't performing well? Thank you.

Upvotes: 3

Views: 2270

Answers (2)

6502
6502

Reputation: 114539

Given the definition of the problem even the working solution is doing way too much. More specifically you need to remember ONLY the max in the stack; something like

s = []
for _ in range(N):
    x = str(input())
    if x[0] == '1':
        v = int(x[2:])
        s.append(v if len(s) == 0 else max(v, s[-1]))
    elif x[0] == '2':
        s.pop()
    else:
        print(s[-1])

should be sufficient.

Upvotes: 1

Eugene Yarmash
Eugene Yarmash

Reputation: 149853

The two solutions are pretty similar, except for the code that returns the maximum element in the stack.

In your solution you use the max() function:

def maxEl(self):
    return max(self.items)

This runs in O(n) time, since max() must check every element in the worst case.

In the other solution maximum values are stored in yet another stack, so getting the current maximum value is just an index operation, which runs in O(1) time:

s.max[-1]

There's also some cost associated with updating the stack of maximums on each push/pop, but those operations are still constant time.

Upvotes: 1

Related Questions