HackerRank ‘Maximum Element’ Solution

Short Problem Definition:

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

  1. 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.
Link

Maximum Element

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

I really enjoyed this problem. I did not see the solution at first, but after it popped up, it was really simple.

Keep two stacks. One for the actual values and one (non-strictly) increasing stack for keeping the maxima.

Solution:

class CustomStack:
    def __init__(self):
        self.stack = []
        self.maxima = []
    
    def push(self, value):
        self.stack.append(value)
        if not self.maxima or value >= self.maxima[-1]:
            self.maxima.append(value)
        
    def printMax(self):
        print self.maxima[-1]
    
    def pop(self):
        value = self.stack.pop()
        if value == self.maxima[-1]:
            self.maxima.pop()

def main():
    cs = CustomStack()
    
    N = int(raw_input())
    
    for _ in xrange(N):
        unknown = raw_input()
        
        command = unknown[0]
        
        if command == '1':
            cmd, value = map(int, unknown.split())
            cs.push(value)
        elif command == '2':
            cs.pop()
        else:
            cs.printMax()
    


if __name__ == '__main__':
    main()

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Sravan Kumar

    Why aren’t you appending the value to the maxima stack if it is not the biggest number? or is my inference incorrect? If what I am saying is true, I feel the answer is incorrect.

    • The maxima stack is a shortcut to answer the query “Print the maximum element in the stack.”. Getting the maximum element is simply reading the head of the maxima stack. If I wanted to push non-max elements onto it, the speed of access would degrade.

      • Sravan Kumar

        What if you had to pop out the last element of the ‘maxima’ stack and what if the value which you are not appending to the stack is the new ‘maximum’ of the maxima stack? I couldn’t understand this particular case.

      • Sravan Kumar

        Thanks for the clarification. Finally I understood why we aren’t appending the last element unless it is greater than the maximum value of maxima stack.

        • Initially I had a bug in the logic, when I only appended greater elements (not greater or equal then). When popping the maxima stack I would get the previous element (which is not true). With the implementation you can see right now, if the elements are equal (8,8,8,8,8) the storage consumption is 2N, which bugs me. If you figure out a way to solve it, please share it 🙂 Glad to have helped anyways!