Problem

Design a max stack that supports push, pop, top, peekMax and popMax.

• push(x) -- Push element x onto stack.
• pop() -- Remove the element on top of the stack and return it.
• top() -- Get the element on the top.
• peekMax() -- Retrieve the maximum element in the stack.
• popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

White Board

Below is the white board:

Code

class Solution:
def isValid(self, s):
st = []
lefts = ["(", "{", "["]
match = {
")":"(",
"}":"{",
"]":"["
}

if len(s) == 0:
return True
if len(s) == 1:
return False

for c in s:
if c in lefts:
st.append(c)
else:
if len(st) == 0:
return False
if st.pop() != match[c]:
return False
#important, need to check st is empty
if len(st) == 0:
return True
else:
return False

def test():
s ="(("
va = Solution().isValid(s)
print(va)

test()

True

Complexity

• Time complexity is O(n*m)
• used additional ds to creat stack

Optimization

Will try to figure out a recursive solution in the future.