design a stack such that getMinimum( ) should be O(1)

Question

EDIT: This fails the "constant space" constraint - it basically doubles the space required. I very much doubt that there's a solution which doesn't do that though, without wrecking the runtime complexity somewhere (e.g. making push/pop O(n)). Note that this doesn't change the complexity of the space required, e.g. if you've got a stack with O(n) space requirements, this will still be O(n) just with a different constant factor.

Non-constant-space solution

Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().

So using your example, we'd have:

Real stack        Min stack

5  --> TOP        1
1                 1
4                 2
6                 2
2                 2

After popping twice you get:

Real stack        Min stack

4                 2
6                 2
2                 2

Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)

(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)

EDIT: There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:

Real stack        Min stack

1  --> TOP        1
5                 1
1                 2
4                 
6                 
2                 

Popping from the above pops from both stacks because 1 == 1, leaving:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

Popping again only pops from the main stack, because 5 > 1:

Real stack        Min stack

1                 1
4                 2
6                 
2                 

Popping again pops both stacks because 1 == 1:

Real stack        Min stack

4                 2
6                 
2                 

This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".

EDIT: Here's an implementation of Pete's evil scheme. I haven't tested it thoroughly, but I think it's okay :)

using System.Collections.Generic;

public class FastMinStack<T>
{
    private readonly Stack<T> stack = new Stack<T>();
    // Could pass this in to the constructor
    private readonly IComparer<T> comparer = Comparer<T>.Default;

    private T currentMin;

    public T Minimum
    {
        get { return currentMin; }
    }

    public void Push(T element)
    {
        if (stack.Count == 0 ||
            comparer.Compare(element, currentMin) <= 0)
        {
            stack.Push(currentMin);
            stack.Push(element);
            currentMin = element;
        }
        else
        {
            stack.Push(element);
        }
    }

    public T Pop()
    {
        T ret = stack.Pop();
        if (comparer.Compare(ret, currentMin) == 0)
        {
            currentMin = stack.Pop();
        }
        return ret;
    }
}

Add a field to hold the minimum value and update it during Pop() and Push(). That way getMinimum() will be O(1), but Pop() and Push() will have to do a little more work.

If minimum value is popped, Pop() will be O(n), otherwise they will still both be O(1). When resizing Push() becomes O(n) as per the Stack implementation.

Here's a quick implementation

public sealed class MinStack {
    private int MinimumValue;
    private readonly Stack<int> Stack = new Stack<int>();

    public int GetMinimum() {
        if (IsEmpty) {
            throw new InvalidOperationException("Stack is empty");
        }
        return MinimumValue;
    }

    public int Pop() {
        var value = Stack.Pop();
        if (value == MinimumValue) {
            MinimumValue = Stack.Min();
        }
        return value;
    }

    public void Push(int value) {
        if (IsEmpty || value < MinimumValue) {
            MinimumValue = value;
        }
        Stack.Push(value);
    }

    private bool IsEmpty { get { return Stack.Count() == 0; } }
}

public class StackWithMin {
    int min;
    int size;
    int[] data = new int[1024];

    public void push ( int val ) {
        if ( size == 0 ) {
            data[size] = val;
            min = val;
        } else if ( val < min) {
            data[size] = 2 * val - min;
            min = val;

            assert (data[size] < min); 
        } else {
            data[size] = val;
        }

        ++size;

        // check size and grow array
    }

    public int getMin () {
        return min;
    }

    public int pop () {
        --size;

        int val = data[size];

        if ( ( size > 0 ) && ( val < min ) ) {
            int prevMin = min;
            min += min - val;
            return prevMin;
        } else {
            return val;
        }
    }

    public boolean isEmpty () {
        return size == 0;
    }

    public static void main (String...args) {
        StackWithMin stack = new StackWithMin();

        for ( String arg: args ) 
            stack.push( Integer.parseInt( arg ) );

        while ( ! stack.isEmpty() ) {
            int min = stack.getMin();
            int val = stack.pop();

            System.out.println( val + " " + min );
        }

        System.out.println();
    }

}

It stores the current minimum explicitly, and if the minimum changes, instead of pushing the value, it pushes a value the same difference the other side of the new minimum ( if min = 7 and you push 5, it pushes 3 instead ( 5-|7-5| = 3) and sets min to 5; if you then pop 3 when min is 5 it sees that the popped value is less than min, so reverses the procedure to get 7 for the new min, then returns the previous min). As any value which doesn't cause a change the current minimum is greater than the current minimum, you have something that can be used to differentiate between values which change the minimum and ones which don't.

In languages which use fixed size integers, you're borrowing a bit of space from the representation of the values, so it may underflow and the assert will fail. But otherwise, it's constant extra space and all operations are still O(1).

Stacks which are based instead on linked lists have other places you can borrow a bit from, for example in C the least significant bit of the next pointer, or in Java the type of the objects in the linked list. For Java this does mean there's more space used compared to a contiguous stack, as you have the object overhead per link:

public class LinkedStackWithMin {
    private static class Link {
        final int value;
        final Link next;

        Link ( int value, Link next ) {
            this.value = value;
            this.next = next;
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            return value;
        }
    }

    private static class MinLink extends Link {
        MinLink ( int value, Link next ) {
            super( value, next );
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            int prevMin = stack.min;
            stack.min = value;
            return prevMin;
        }
    }

    Link top;
    int min;

    public LinkedStackWithMin () {
    }

    public void push ( int val ) {
        if ( ( top == null ) || ( val < min ) ) {
            top = new MinLink(min, top);
            min = val;
        } else {
            top = new Link(val, top);
        }
    }

    public int pop () {
        return top.pop(this);
    }

    public int getMin () {
        return min;
    }

    public boolean isEmpty () {
        return top == null;
    }

In C, the overhead isn't there, and you can borrow the lsb of the next pointer:

typedef struct _stack_link stack_with_min;

typedef struct _stack_link stack_link;

struct _stack_link {
    size_t  next;
    int     value;
};

stack_link* get_next ( stack_link* link ) 
{
    return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}

bool is_min ( stack_link* link )
{
    return ( link -> next & 1 ) ! = 0;
}

void push ( stack_with_min* stack, int value )
{
    stack_link *link = malloc ( sizeof( stack_link ) );

    link -> next = ( size_t ) stack -> next;

    if ( (stack -> next == 0) || ( value == stack -> value ) ) {
        link -> value = stack -> value;
        link -> next |= 1; // mark as min
    } else {
        link -> value = value;
    }

    stack -> next = link;
}

etc.;

However, none of these are truly O(1). They don't require any more space in practice, because they exploit holes in the representations of numbers, objects or pointers in these languages. But a theoretical machine which used a more compact representation would require an extra bit to be added to that representation in each case.

I found a solution that satisfies all the constraints mentioned (constant time operations) and constant extra space.

The idea is to store the difference between min value and the input number, and update the min value if it is no longer the minimum.

The code is as follows:

public class MinStack {
    long min;
    Stack<Long> stack;

    public MinStack(){
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        } else {
            stack.push(x - min); //Could be negative if min value needs to change
            if (x < min) min = x;
        }
    }

    public int pop() {
        if (stack.isEmpty()) return;

        long pop = stack.pop();

        if (pop < 0) {
            long ret = min
            min = min - pop; //If negative, increase the min value
            return (int)ret;
        }
        return (int)(pop + min);

    }

    public int top() {
        long top = stack.peek();
        if (top < 0) {
            return (int)min;
        } else {
           return (int)(top + min);
        }
    }

    public int getMin() {
        return (int)min;
    }
}

Credit goes to: https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack

Well, what are the runtime constraints of push and pop? If they are not required to be constant, then just calculate the minimum value in those two operations (making them O(n)). Otherwise, I don't see how this can be done with constant additional space.

We can do this in O(n) time and O(1) space complexity, like so:

class MinStackOptimized:
  def __init__(self):
      self.stack = []
      self.min = None

  def push(self, x): 
      if not self.stack:
          # stack is empty therefore directly add
          self.stack.append(x)
          self.min = x 
      else:
          """
          Directly add (x-self.min) to the stack. This also ensures anytime we have a 
          negative number on the stack is when x was less than existing minimum
          recorded thus far.
          """
          self.stack.append(x-self.min)
          if x < self.min:
              # Update x to new min
              self.min = x 

  def pop(self):
      x = self.stack.pop()
      if x < 0:
          """ 
          if popped element was negative therefore this was the minimum
          element, whose actual value is in self.min but stored value is what
          contributes to get the next min. (this is one of the trick we use to ensure
          we are able to get old minimum once current minimum gets popped proof is given
          below in pop method), value stored during push was:
          (x - self.old_min) and self.min = x therefore we need to backtrack
          these steps self.min(current) - stack_value(x) actually implies to
              x (self.min) - (x - self.old_min)
          which therefore gives old_min back and therefore can now be set
          back as current self.min.
          """
          self.min = self.min - x 

  def top(self):
      x = self.stack[-1]
      if x < 0:
          """ 
          As discussed above anytime there is a negative value on stack, this
          is the min value so far and therefore actual value is in self.min,
          current stack value is just for getting the next min at the time
          this gets popped.
          """
          return self.min
      else:
          """ 
          if top element of the stack was positive then it's simple, it was
          not the minimum at the time of pushing it and therefore what we did
          was x(actual) - self.min(min element at current stage) let's say `y`
          therefore we just need to reverse the process to get the actual
          value. Therefore self.min + y, which would translate to
              self.min + x(actual) - self.min, thereby giving x(actual) back
          as desired.
          """
          return x + self.min

  def getMin(self):
      # Always self.min variable holds the minimum so for so easy peezy.
      return self.min

Let's assume the stack which we will be working on is this :

6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8

In the above representation the stack is only built by left value's the right value's [minvalue] is written only for illustration purpose which will be stored in one variable.

The actual problem is when the value which is the minimum value gets removed: At that point how can we know what is the next minimum element without iterating over the stack.

Like for example in our stack when 6 gets popped we know that, this is not the minimum element because the minimum element is 2, so we can safely remove this without updating our min value.

But when we pop 2, we can see that the minimum value is 2 right now and if this gets popped out then we need to update the minimum value to 3.

Point1:

Now if you observe carefully we need to generate minvalue=3 from this particular state [2 , minvalue=2].
Or if you go deeper in the stack we need to generate minvalue=7 from this particular state [3 , minvalue=3]
or if you go deeper still in the stack then we need to generate minvalue=8 from this particular state [7 , minvalue=7]

Did you notice something in common in all of the above three cases? The value which we need to generate depends upon two variable which are both equal. Correct.
Why is this happening because when we push some element smaller then the current minvalue, then we basically push that element in the stack and updated the same number in minvalue also.

Point2:

So we are basically storing duplicate of the same number once in stack and once in minvalue variable.
We need to focus on avoiding this duplication and store something useful data in the stack or the minvalue to generate the previous minimum as shown in CASES above.

Let's focus on what should we store in stack when the value to store in push is less than the minimum value. Let's name this variable y, so now our stack will look something like this:

6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8

I have renamed them as y1,y2,y3 to avoid confusion that all of them will have same value.

Point3:

Now let's try to find some constraint's over y1, y2 and y3. Do you remember when exactly we need to update the minvalue while doing pop(), only when we have popped the element which is equal to the minvalue.
If we pop something greater than the minvalue then we don't have to update minvalue.
So to trigger the update of minvalue, y1,y2&y3 should be smaller than there corresponding minvalue. [We are avoiding equality to avoid duplicate[Point2]]
so the constrain is [ y < minValue ].

Now let's come back to populate y, we need to generate some value and put y at the time of push, remember.
Let's take the value which is coming for push to be x which is less that the prevMinvalue, and the value which we will actually push in stack to be y.
So one thing is obvious that the newMinValue=x, and y < newMinvalue.

Now we need to calculate y(remember y can be any number which is less than newMinValue(x) so we need to find some number which can fulfil our constraint) with the help of prevMinvalue and x(newMinvalue).

Let's do the math:
    x < prevMinvalue [Given]
    x - prevMinvalue < 0 
    x - prevMinValue + x < 0 + x [Add x on both side]
    2*x - prevMinValue < x      
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].

So at the time of pushing x if it is less than prevMinvalue then we push y[2*x-prevMinValue] and update newMinValue = x .

And at the time of pop if the stack contains something less than the minValue then that's our trigger to update the minValue. We have to calculate prevMinValue from the curMinValue and y.
  y = 2*curMinValue - prevMinValue [Proved]
  prevMinValue = 2*curMinvalue - y .

2*curMinValue - y is the number which we need to update now to the prevMinValue.

Code for the same logic is shared below with O(1) time and O(1) space complexity.

// C++ program to implement a stack that supports 
// getMinimum() in O(1) time and O(1) extra space. 
#include <bits/stdc++.h> 
using namespace std; 
  
// A user defined stack that supports getMin() in 
// addition to push() and pop() 
struct MyStack 
{ 
    stack<int> s; 
    int minEle; 
  
    // Prints minimum element of MyStack 
    void getMin() 
    { 
        if (s.empty()) 
            cout << "Stack is empty\n"; 
  
        // variable minEle stores the minimum element 
        // in the stack. 
        else
            cout <<"Minimum Element in the stack is: "
                 << minEle << "\n"; 
    } 
  
    // Prints top element of MyStack 
    void peek() 
    { 
        if (s.empty()) 
        { 
            cout << "Stack is empty "; 
            return; 
        } 
  
        int t = s.top(); // Top element. 
  
        cout << "Top Most Element is: "; 
  
        // If t < minEle means minEle stores 
        // value of t. 
        (t < minEle)? cout << minEle: cout << t; 
    } 
  
    // Remove the top element from MyStack 
    void pop() 
    { 
        if (s.empty()) 
        { 
            cout << "Stack is empty\n"; 
            return; 
        } 
  
        cout << "Top Most Element Removed: "; 
        int t = s.top(); 
        s.pop(); 
  
        // Minimum will change as the minimum element 
        // of the stack is being removed. 
        if (t < minEle) 
        { 
            cout << minEle << "\n"; 
            minEle = 2*minEle - t; 
        } 
  
        else
            cout << t << "\n"; 
    } 
  
    // Removes top element from MyStack 
    void push(int x) 
    { 
        // Insert new number into the stack 
        if (s.empty()) 
        { 
            minEle = x; 
            s.push(x); 
            cout <<  "Number Inserted: " << x << "\n"; 
            return; 
        } 
  
        // If new number is less than minEle 
        if (x < minEle) 
        { 
            s.push(2*x - minEle); 
            minEle = x; 
        } 
  
        else
           s.push(x); 
  
        cout <<  "Number Inserted: " << x << "\n"; 
    } 
}; 
  
// Driver Code 
int main() 
{ 
    MyStack s; 
    s.push(3); 
    s.push(5); 
    s.getMin(); 
    s.push(2); 
    s.push(1); 
    s.getMin(); 
    s.pop(); 
    s.getMin(); 
    s.pop(); 
    s.peek(); 
  
    return 0; 
}