Interview Question: Stack which returns min element in O(1)

Stack is a LIFO(Last-In-First-Out) list of elements where Push (Insert an element at top of Stack) & Pop (Delete top element from the Stack) operations takes constant (O(1)) time.

Design a Stack such that the operation of getminimum()  (function returning minimum element of the stack) also takes constant time.

Please note that it will only return the current minimum element from the stack and will not delete (pop) any element from the stack.

In this method we use 2 stacks

1. main Stack, S
2. minStack to hold the current minimum element.

We modify the Push operation of the original Stack, S

• If the top element of MinStack < element being inserted
• Also Insert in the MinStack

We modify the Pop operation of the original Stack, S

• Also Pop top element from MinStack

getMinimum function will return (and not pop) the top element from MinStack)

At any point, the Stack and MinStack will look as shown below:

 

If we pop 0 from Stack, 0 will be poped from MinStack and then getminimum will return 4 (minimum element in Stack)

In this method, we modify the Node structure to also hold a pointer to the next minimum,

struct Node
{
    int data;
    Node* link;
    Node* nextMin; // either NULL or points to the next minimum element
   
    // Default Constructor. Set the pointers to NULL
    Node(int d): data(d), link(NULL), nextMin(NULL){}
};

If you don't know C++ and wonder, how a function comes in the definition of struct, please ignore it for the time being, ,lets focus on the logic and not on the syntax.

Stack will have one additional pointer (along with top pointer) called min. This will point to the current minimum element in the Stack (and will be updated on each push & pop operation). So our Stack class will look like below:

class MinStack
{
private:
    Node* top;
    Node* min;
public:
    MinStack():top(NULL),min(NULL){}
   
    void push(int d);
    int pop();
    int getMinimum();
   
    // Just to print All the elements in the Stack.
    void printStack();
};

Again, don't get confused in the syntax of C++, we just have 3 functions, push, pop & getMinimum. and a helper function printStack (don't need this actually).
 
We Now modify the push & pop operation as below

Push Operation:

 - If stack is Empty
    - push an element in it and set min & top point to it.
 - else
    - push element on the top (its nextMin will be NULL)
    - if(element inserted is less than element at min)
         - top - > nextMin = min
         - min = top;
   
Pop Operation:

 - If top element is also min element
    - min = min->nextMin
 - Pop the element at Top

getMinimum operation will return the element pointed to by min pointer.

At any point the stack will look something like below (the red arrows shows nextMin pointers, If red arrow is missing for some element, it means its nextMin pointer is NULL)

Code: Let me just copy paste the entire code for you guys this time :)

There are 2 files

• MyStack.h - Having the declaration of Node & the MinStack class
• MyStack.cpp - Having the definitions of all the function from MinStack class.

I have written the code in XCode 3.2.5 on MAC OSX

/*
* MinStack.h
*
* Created by Kamal Rawat on 31/01/12.
* Copyright 2012 __MyCompanyName__. All rights reserved.
*/
#include <iostream>

struct Node
{
   int data;
   Node* link;
   Node* nextMin;
   
   // Constructor.
   Node(int d):data(d), link(NULL), nextMin(NULL){}
};

class MinStack
{
private:
   Node* top;
   Node* min;
public:
   MinStack():top(NULL),min(NULL){}
   void push(int d);
   int pop();
   int getMinimum();
   
   // Just to print All the elements in the Stack.
   void printStack();
};

------------------------------
File: MinStack.cpp

/*
* MinStack.cpp
*
* Created by Kamal Rawat on 31/01/12.
* Copyright 2012 __MyCompanyName__. All rights reserved.
*/

#include "MinStack.h"
#include <iostream>
using namespace std;


void MinStack::push(int d)
{
   Node* t = new Node(d);
   
   if(top == NULL) {
      top = min = t;
      
   } else {
      t->link = top;
      top = t;
      
      // Element inserted is less than minimum
      // Set it as the new minimum
      if(min->data > top->data) {
         top->nextMin = min;
         min = top;
      }
   }
}

int MinStack::pop()
{
   // Check for empty stack
   if(top == NULL) return -1;
      
   // If dileating the minimum, set the next minimum
   if(min == top) {
      min = min->nextMin;
   }
   
   int d = top->data;
   Node* t = top;
   top = top->link;
   delete t;
   return d;
}

int MinStack::getMinimum()
{
   // If Stack is Empty Same check as (top == NULL)
   // Since we are not deleting the elements here, we don't need to
   // update any pointer, just return the minimum element.
   if(min == NULL) {
      return -1;
   }
   else {
      return min->data;
   }
}

void MinStack::printStack()
{
   for (Node*t = top; t!=NULL; t=t->link) {
      cout << " " << t->data;
   }
}