LeetCode 155. Design Min Stack, Max Stack, Median Stack

relevant problems:

• LeetCode 716. Max Stack
• PAT Stack

Problem Clarification

Stack is a fundamental data structure for LIFO (Last In First Out), which basically supports:

• push: add an element onto the stack
• pop: remove the element on top of the stack
• top: get the element on top of the stack

Now design an advanced stack that also supports:

• peekMin/Max/Median: get the min/max/median of all the elments in the stack
• popMin/Max/Median: remove the min/max/median element in the stack (if multiple exist, only remove the top-most one)

* Here in MedianStack, the definition for median is a little different from its mathematical definition: with N elements, the median value is defined to be the $N/2$-th smallest element if N is even, or $(N+1)/2$-th if N is odd.

Analysis

• vanilla Stack: when peekM is called, loop in the stack to find M (i.e. Min/Max/Median); when popM is called, rebuild the latter part of the stack, i.e. pop until M (calculated from peekM) is met, then push the popped elements back; push, pop, and top in $O(1)$, peekM and popM in $O(N)$.
• MinStack/MaxStack: use extra space to remember the min/max values we’ve seen alongside the elements added; push, pop, top, and peekM in $O(1)$, popM in $O(N)$.
  1. (most straightforward) create a pair (value, min_value) for each element to add onto the stack
  2. (improvement) save space for consecutive identical min values by using a separate min_value stack; when adding each element onto the vanilla stack, also add the element onto the min_value stack iff (i.e. if and only if) the element is less than or equals to the current min value
  3. (improvement) save more space for consecutive identical min values in min_value by using a min_value_count stack: when adding each element onto the vanilla stack, also add [element, 1] onto the min_value_count stack iff the element is less than the current min value, or update the count iff the element equals to the current min value
  4. (devoted to improving popM) use double linked list (to faster remove node) and TreeMap (to retrieve min/max dynamically in $O(1)$); see LeetCode MaxStack Solution - Approach #2
• MedianStack: use extra space to record the sorting info alongside a vanilla stack to record the element sequence; push and pop in $O(logN)$, peekMedian in $O(1)$. (note: the insert/remove operation actually cost $O(N)$ in python list)
  1. use a sorted list and find where to insert/remove elements using binary search; get median directly by index in the sorted list.
  2. use a max heap to store the smaller half, and a min heap to store the larger half; for each element, heap push it to and pop the heap of larger size (if two heaps are of equal size, choose any one), then heap push the popped element to the other heap.

Code

* Code here have minor differences in regard to methods implemented (popM may not be required), method names (“peek” and “get”), and return types (whether pop returns None), in order to be applied directly on LeetCode.

• MinStack #3

  class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
  
    def push(self, x):
        self.stack.append(x)
  
        if not self.min_stack or x < self.min_stack[-1][0]:
            self.min_stack.append([x, 1])
        elif x == self.min_stack[-1][0]:
            self.min_stack[-1][1] += 1
  
    def pop(self):
        if self.stack[-1] == self.min_stack[-1][0]:
            if self.min_stack[-1][1] == 1:
                self.min_stack.pop()
            else:
                self.min_stack[-1][1] -= 1
        return self.stack.pop()
  
    def top(self):
        return self.stack[-1]
  
    def getMin(self):
        return self.min_stack[-1][0]
  

• MaxStack #1

  class MaxStack:
    def __init__(self):
        self.stack = []
  
    def push(self, x):
        if not self.stack:
            self.stack.append((x, x))
        else:
            cur_max = max(self.stack[-1][1], x)
            self.stack.append((x, cur_max))
  
    def pop(self):
        return self.stack.pop()[0]
  
    def top(self):
        return self.stack[-1][0]
  
    def peekMax(self):
        return self.stack[-1][1]
  
    def popMax(self):
        m = self.stack[-1][1]
        tail = []
        while self.stack[-1][0] != m:
            tail.append(self.pop())
        self.pop()
        for x in reversed(tail):
            self.push(x)
        return m
  

• MedianStack