design a stack such that getMinimum( ) should be O

Question

This is one of an interview question. You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.

For example: consider the below example

case #1

5  --> TOP
1
4
6
2

When getMinimum() is called it should return 1, which is the minimum element 
in the stack. 

case #2

stack.pop()
stack.pop()

Note: Both 5 and 1 are poped out of the stack. So after this, the stack
looks like,

4  --> TOP
6
2

When getMinimum() is called is should return 2 which is the minimum in the 
stack.

Constriants:

1. getMinimum should return the minimum value in O(1)
2. Space constraint also has to be considered while designing it and if you use extra space, it should be of constant space.

Answer 1

I found this solution here

struct StackGetMin {
  void push(int x) {
    elements.push(x);
    if (minStack.empty() || x <= minStack.top())
      minStack.push(x);
  }
  bool pop() {
    if (elements.empty()) return false;
    if (elements.top() == minStack.top())
      minStack.pop();
    elements.pop();
    return true;
  }
  bool getMin(int &min) {
    if (minStack.empty()) {
      return false;
    } else {
      min = minStack.top();
      return true;
    }
  }
  stack<int> elements;
  stack<int> minStack;
};

Answer 2

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Solution 
{
    public class MinStack
    {
        public MinStack()
        {
            MainStack=new Stack<int>();
            Min=new Stack<int>();
        }

        static Stack<int> MainStack;
        static Stack<int> Min;

        public void Push(int item)
        {
            MainStack.Push(item);

            if(Min.Count==0 || item<Min.Peek())
                Min.Push(item);
        }

        public void Pop()
        {
            if(Min.Peek()==MainStack.Peek())
                Min.Pop();
            MainStack.Pop();
        }
        public int Peek()
        {
            return MainStack.Peek();
        }

        public int GetMin()
        {
            if(Min.Count==0)
                throw new System.InvalidOperationException("Stack Empty"); 
            return Min.Peek();
        }
    }
}

Answer 3

You could extend your original stack class and just add the min tracking to it. Let the original parent class handle everything else as usual.

public class StackWithMin extends Stack<Integer> {  

    private Stack<Integer> min;

    public StackWithMin() {
        min = new Stack<>();
    }

    public void push(int num) {
        if (super.isEmpty()) {
            min.push(num);
        } else if (num <= min.peek()) {
            min.push(num);
        }
        super.push(num);
    }

    public int min() {
        return min.peek();
    }

    public Integer pop() {
        if (super.peek() == min.peek()) {
            min.pop();
        }
        return super.pop();
    }   
}

Answer 4

Here is my version of implementation.

 struct MyStack {
    int element;
    int *CurrentMiniAddress;
 };

 void Push(int value)
 {
    // Create you structure and populate the value
    MyStack S = new MyStack();
    S->element = value;

    if(Stack.Empty())
    {    
        // Since the stack is empty, point CurrentMiniAddress to itself
        S->CurrentMiniAddress = S;

    }
    else
    {
         // Stack is not empty

         // Retrieve the top element. No Pop()
         MyStack *TopElement = Stack.Top();

         // Remember Always the TOP element points to the
         // minimum element in ths whole stack
         if (S->element CurrentMiniAddress->element)
         {
            // If the current value is the minimum in the whole stack
            // then S points to itself
            S->CurrentMiniAddress = S;
         }
             else
             {
                 // So this is not the minimum in the whole stack
                 // No worries, TOP is holding the minimum element
                 S->CurrentMiniAddress = TopElement->CurrentMiniAddress;
             }

    }
        Stack.Add(S);
 }

 void Pop()
 {
     if(!Stack.Empty())
     {
        Stack.Pop();
     }  
 }

 int GetMinimum(Stack &stack)
 {
       if(!stack.Empty())
       {
            MyStack *Top  = stack.top();
            // Top always points to the minimumx
            return  Top->CurrentMiniAddress->element;
        }
 }

Answer 5

Here's the PHP implementation of what explained in Jon Skeet's answer as the slightly better space complexity implementation to get the maximum of stack in O(1).

<?php

/**
 * An ordinary stack implementation.
 *
 * In real life we could just extend the built-in "SplStack" class.
 */
class BaseIntegerStack
{
    /**
     * Stack main storage.
     *
     * @var array
     */
    private $storage = [];

    // ------------------------------------------------------------------------
    // Public API
    // ------------------------------------------------------------------------

    /**
     * Pushes to stack.
     *
     * @param  int $value New item.
     *
     * @return bool
     */
    public function push($value)
    {
        return is_integer($value)
            ? (bool) array_push($this->storage, $value)
            : false;
    }

    /**
     * Pops an element off the stack.
     *
     * @return int
     */
    public function pop()
    {
        return array_pop($this->storage);
    }

    /**
     * See what's on top of the stack.
     *
     * @return int|bool
     */
    public function top()
    {
        return empty($this->storage)
            ? false
            : end($this->storage);
    }

    // ------------------------------------------------------------------------
    // Magic methods
    // ------------------------------------------------------------------------

    /**
     * String representation of the stack.
     *
     * @return string
     */
    public function __toString()
    {
        return implode('|', $this->storage);
    }
} // End of BaseIntegerStack class

/**
 * The stack implementation with getMax() method in O(1).
 */
class Stack extends BaseIntegerStack
{
    /**
     * Internal stack to keep track of main stack max values.
     *
     * @var BaseIntegerStack
     */
    private $maxStack;

    /**
     * Stack class constructor.
     *
     * Dependencies are injected.
     *
     * @param BaseIntegerStack $stack Internal stack.
     *
     * @return void
     */
    public function __construct(BaseIntegerStack $stack)
    {
        $this->maxStack = $stack;
    }

    // ------------------------------------------------------------------------
    // Public API
    // ------------------------------------------------------------------------

    /**
     * Prepends an item into the stack maintaining max values.
     *
     * @param  int $value New item to push to the stack.
     *
     * @return bool
     */
    public function push($value)
    {
        if ($this->isNewMax($value)) {
            $this->maxStack->push($value);
        }

        parent::push($value);
    }

    /**
     * Pops an element off the stack maintaining max values.
     *
     * @return int
     */
    public function pop()
    {
        $popped = parent::pop();

        if ($popped == $this->maxStack->top()) {
            $this->maxStack->pop();
        }

        return $popped;
    }

    /**
     * Finds the maximum of stack in O(1).
     *
     * @return int
     * @see push()
     */
    public function getMax()
    {
        return $this->maxStack->top();
    }

    // ------------------------------------------------------------------------
    // Internal helpers
    // ------------------------------------------------------------------------

    /**
     * Checks that passing value is a new stack max or not.
     *
     * @param  int $new New integer to check.
     *
     * @return boolean
     */
    private function isNewMax($new)
    {
        return empty($this->maxStack) OR $new > $this->maxStack->top();
    }

} // End of Stack class

// ------------------------------------------------------------------------
// Stack Consumption and Test
// ------------------------------------------------------------------------
$stack = new Stack(
    new BaseIntegerStack
);

$stack->push(9);
$stack->push(4);
$stack->push(237);
$stack->push(5);
$stack->push(556);
$stack->push(15);

print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";

print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";

print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";

print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";

print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n";

// Here's the sample output:
//
// Stack: 9|4|237|5|556|15
// Max: 556
//
// Pop: 15
// Pop: 556
//
// Stack: 9|4|237|5
// Max: 237
//
// Pop: 5
// Pop: 237
//
// Stack: 9|4
// Max: 9