LeetCode: Min Stack Posted on January 10, 2018July 26, 2020 by braindenny Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Similar Problems: Max Stack CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #oodesign, #designstack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) — Push element x onto stack. pop() — Removes the element on top of the stack. top() — Get the top element. getMin() — Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/min-stack ## Basic Ideas: List with elements of (value, min_value) ## -2 0 -3 4 ## linked list: ## (-2, -2), (0, -2), (-3, -3), (4, -3) ## ## length: element count ## Complexity: Time: O(1), Space: O(n) class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.length = 0 self.min_value = None self.values = [] def push(self, x): """ :type x: int :rtype: void """ if self.length == 0: element = (x, x) self.min_value = x else: if x > self.min_value: element = (x, self.min_value) else: self.min_value = x element = (x, x) self.values.append(element) self.length += 1 def pop(self): """ :rtype: void """ if self.length == 0: return if self.length == 1: self.min_value = None else: (x, previous_min_value) = self.values[-2] self.min_value = previous_min_value self.values.pop() self.length -= 1 def top(self): """ :rtype: int """ if len(self.values) == 0: return None else: (x, _min_value) = self.values[-1] return x def getMin(self): """ :rtype: int """ return self.min_value Post Views: 1