Friedrich Ewald My Personal Website

Leetcode: Minimum Stack

Create a stack implementation that is able to return the minimum element as well as push and pop elements, all in constant time O(1). I used the builtin heapq library which provides a heap implementation. This works realiably to find the minimum element. When deleting element from the stack structure we don’t know where on the heap the element is stored. Any type of scanning the heap would violate the O(1) requirement. Instead, I chose to store the deleted elements in a dictionary. If the min element should be returned, the tombstones are checked. If the element is marked as deleted, the next item is checked, and so on. I use a list as the actual stack because append and pop perform both in O(1).

import heapq

class MinStack:
  def __init__(self):
    self._s = []
    self._h = []
    self._popped = {}

  def push(self, val: int) -> None:
    self._s.append(val)
    heapq.heappush(self._h, val)

  def pop(self) -> None:
    item = self._s.pop()
    
    if self._h[0] == item:
      heapq.heappop(self._h)
    else:
      if item not in self._popped:
          self._popped[item] = 0
      self._popped[item]  += 1

  def top(self) -> int:
    return self._s[-1]

  def getMin(self) -> int:
    while self._h[0] in self._popped:
      item = heapq.heappop(self._h)
      self._popped[item] -= 1
      if self._popped[item] == 0:
        del self._popped[item]
    return self._h[0]
Runtime: 157 ms, faster than 12.25% of Python3 online submissions for Min Stack. Memory Usage: 18 MB, less than 60.07% of Python3 online submissions for Min Stack.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.