Jagadish, K.

Implement a Max/Min Stack

Published on

This is a variation on the a Leetcode question

Question

Design a structure that is similar to a stack such that it supports push, pop, top, and retrieving the minimum and maximum elements 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. getMax() — Retrieve the maximum element in the stack.

Solution

In a usual stack data structure, time to fetch the max or min item would depend on the order in which elements had been pushed into it. You would have to pop out all items and find the minimum element, and push back all the items into it such that the items are not lost.

To implement it with constant retrieval time, you can use an additinoal dequeue structure such that, the head of the queue gets the global minima, and the tail gets the global maxima. It stores duplicate values of the minima and maxima such that, even if a ‘max’ or ‘min’ element is popped out, you will still know the global maxima/minima.

Since JS doesn’t have a queue structure, we use an array to achieve that behavior.

const MaxMinStack = function(){
  let MAX = Number.MIN_SAFE_INTEGER;
  let MIN = Number.MAX_SAFE_INTEGER;

  let size = 0;
  const itemStack = [];
  const dequeue = [];

  const push = (item) => {
    if (item >= MAX){
      MAX = item;
      dequeue.push(item);
    } else if (item <= MIN){
      MIN = item;
      dequeue.unshift(item);
    }

    itemStack.push(item);
    size++;
  }

  const pop = () => {
    if(!size) return;
    const item = itemStack.pop();

    if(item == MAX){
      dequeue.pop();
      MAX = dequeue[dequeue.length - 1];
    } else if(item == MIN){
      dequeue.shift();
      MIN = dequeue[0];
    }

    size--;

    return item;
  }

  const top = () => itemStack[size - 1];

  const getMin = () => size ? dequeue[0] : 'Stack is empty';
  const getMax = () => size ? dequeue[size - 1] : 'Stack is empty';

  return {
    push,
    pop,
    top,
    getMin,
    getMax,
  }
};

If you think somebody would benefit from reading this post, please share away and help me reach more people.