Min Stack Class
Programming Interview
Hard
8 views
Problem Description
You will receive q commands: PUSH x, POP, MIN. Create MinStack class and for MIN output current minimum or EMPTY.
Input Format
First line q. Next q lines commands.
Output Format
Outputs for MIN.
Sample Test Case
Input:
7
PUSH 5
PUSH 2
MIN
POP
MIN
POP
MIN
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
q=int(lines[0].strip())
class MinStack:
def __init__(self):
self.a=[]
self.m=[]
def push(self,x):
self.a.append(x)
self.m.append(x if not self.m else (x if x<self.m[-1] else self.m[-1]))
def pop(self):
if self.a:
self.a.pop()
self.m.pop()
def getmin(self):
return self.m[-1] if self.m else None
st=MinStack()
out=[]
for i in range(1,1+q):
parts=(lines[i] if i<len(lines) else '').split()
if not parts: continue
if parts[0]=='PUSH':
st.push(int(parts[1]))
elif parts[0]=='POP':
st.pop()
else:
v=st.getmin()
out.append(str(v) if v is not None else 'EMPTY')
print('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!