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 think you can simply use a LinkedList in your stack implementation.

First time you push a value, you put this value as the linkedlist head.

then each time you push a value, if the new value < head.data, make a prepand operation ( which means the head becomes the new value )

if not, then make an append operation.

When you make a pop(), you check if min == linkedlist.head.data, if yes, then head=head.next;

Here is my code.

public class Stack {

int[] elements;
int top;
Linkedlists min;

public Stack(int n) {
    elements = new int[n];
    top = 0;
    min = new Linkedlists();
}

public void realloc(int n) {
    int[] tab = new int[n];
    for (int i = 0; i < top; i++) {
        tab[i] = elements[i];
    }

    elements = tab;
}

public void push(int x) {
    if (top == elements.length) {
        realloc(elements.length * 2);
    }
    if (top == 0) {
        min.pre(x);
    } else if (x < min.head.data) {
        min.pre(x);
    } else {
        min.app(x);
    }
    elements[top++] = x;
}

public int pop() {

    int x = elements[--top];
    if (top == 0) {

    }
    if (this.getMin() == x) {
        min.head = min.head.next;
    }
    elements[top] = 0;
    if (4 * top < elements.length) {
        realloc((elements.length + 1) / 2);
    }

    return x;
}

public void display() {
    for (Object x : elements) {
        System.out.print(x + " ");
    }

}

public int getMin() {
    if (top == 0) {
        return 0;
    }
    return this.min.head.data;
}

public static void main(String[] args) {
    Stack stack = new Stack(4);
    stack.push(2);
    stack.push(3);
    stack.push(1);
    stack.push(4);
    stack.push(5);
    stack.pop();
    stack.pop();
    stack.pop();
    stack.push(1);
    stack.pop();
    stack.pop();
    stack.pop();
    stack.push(2);
    System.out.println(stack.getMin());
    stack.display();

}

 }

Answer 2

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;
    }
}

Answer 3

I am posting the complete code here to find min and max in a given stack.

Time complexity will be O(1)..

package com.java.util.collection.advance.datastructure;

/**
 * 
 * @author vsinha
 *
 */
public abstract interface Stack<E> {

    /**
     * Placing a data item on the top of the stack is called pushing it
     * @param element
     * 
     */
    public abstract void push(E element);


    /**
     * Removing it from the top of the stack is called popping it
     * @return the top element
     */
    public abstract E pop();

    /**
     * Get it top element from the stack and it 
     * but the item is not removed from the stack, which remains unchanged
     * @return the top element
     */
    public abstract E peek();

    /**
     * Get the current size of the stack.
     * @return
     */
    public abstract int size();


    /**
     * Check whether stack is empty of not.
     * @return true if stack is empty, false if stack is not empty
     */
    public abstract boolean empty();



}



package com.java.util.collection.advance.datastructure;

@SuppressWarnings("hiding")
public abstract interface MinMaxStack<Integer> extends Stack<Integer> {

    public abstract int min();

    public abstract int max();

}


package com.java.util.collection.advance.datastructure;

import java.util.Arrays;

/**
 * 
 * @author vsinha
 *
 * @param <E>
 */
public class MyStack<E> implements Stack<E> {

    private E[] elements =null;
    private int size = 0;
    private int top = -1;
    private final static int DEFAULT_INTIAL_CAPACITY = 10;


    public MyStack(){
        // If you don't specify the size of stack. By default, Stack size will be 10
        this(DEFAULT_INTIAL_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public MyStack(int intialCapacity){
        if(intialCapacity <=0){
            throw new IllegalArgumentException("initial capacity can't be negative or zero");
        }
        // Can't create generic type array
        elements =(E[]) new Object[intialCapacity];
    }

    @Override
    public void push(E element) {
        ensureCapacity();
        elements[++top] = element;
        ++size;
    }

    @Override
    public E pop() {
        E element = null;
        if(!empty()) {
            element=elements[top];
            // Nullify the reference
            elements[top] =null;
            --top;
            --size;
        }
        return element;
    }

    @Override
    public E peek() {
        E element = null;
        if(!empty()) {
            element=elements[top];
        }
        return element;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean empty() {
        return size == 0;
    }

    /**
     * Increases the capacity of this <tt>Stack by double of its current length</tt> instance, 
     * if stack is full 
     */
    private void ensureCapacity() {
        if(size != elements.length) {
            // Don't do anything. Stack has space.
        } else{
            elements = Arrays.copyOf(elements, size *2);
        }
    }

    @Override
    public String toString() {
        return "MyStack [elements=" + Arrays.toString(elements) + ", size="
                + size + ", top=" + top + "]";
    }


}


package com.java.util.collection.advance.datastructure;

/**
 * Time complexity will be O(1) to find min and max in a given stack.
 * @author vsinha
 *
 */
public class MinMaxStackFinder extends MyStack<Integer> implements MinMaxStack<Integer> {

    private MyStack<Integer> minStack;

    private MyStack<Integer> maxStack;

    public MinMaxStackFinder (int intialCapacity){
        super(intialCapacity);
        minStack =new MyStack<Integer>();
        maxStack =new MyStack<Integer>();

    }
    public void push(Integer element) {
        // Current element is lesser or equal than min() value, Push the current element in min stack also.
        if(!minStack.empty()) {
            if(min() >= element) {
                minStack.push(element);
            }
        } else{
            minStack.push(element);
        }
        // Current element is greater or equal than max() value, Push the current element in max stack also.
        if(!maxStack.empty()) {
            if(max() <= element) {
                maxStack.push(element);
            }
        } else{
            maxStack.push(element);
        }
        super.push(element);
    }


    public Integer pop(){
        Integer curr = super.pop();
        if(curr !=null) {
            if(min() == curr) {
                minStack.pop();
            } 

            if(max() == curr){
                maxStack.pop();
            }
        }
        return curr;
    }


    @Override
    public int min() {
        return minStack.peek();
    }

    @Override
    public int max() {
        return maxStack.peek();
    }


    @Override
    public String toString() {
        return super.toString()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
                + maxStack + "]" ;
    }




}

// You can use the below program to execute it.

package com.java.util.collection.advance.datastructure;

import java.util.Random;

public class MinMaxStackFinderApp {

    public static void main(String[] args) {
        MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
        Random random =new Random();
        for(int i =0; i< 10; i++){
            stack.push(random.nextInt(100));
        }
        System.out.println(stack);
        System.out.println("MAX :"+stack.max());
        System.out.println("MIN :"+stack.min());

        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();

        System.out.println(stack);
        System.out.println("MAX :"+stack.max());
        System.out.println("MIN :"+stack.min());
    }
}

Let me know if you are facing any issue

Thanks, Vikash

Answer 4

struct Node {
    let data: Int
    init(_ d:Int){
        data = d
    }
}

struct Stack {
    private var backingStore = [Node]()
    private var minArray = [Int]()

    mutating func push(n:Node) {
        backingStore.append(n)
        minArray.append(n.data)
        minArray.sort(>)
        minArray
    }

    mutating func pop() -> Node? {
        if(backingStore.isEmpty){
            return nil
        }

        let n = backingStore.removeLast()

        var found = false
        minArray = minArray.filter{
            if (!found && $0 == n.data) {
                found = true
                return false
            }
            return true
        }
        return n
    }

    func min() -> Int? {
        return minArray.last
    }
}

Answer 5

class FastStack {

    private static class StackNode {
        private Integer data;
        private StackNode nextMin;

        public StackNode(Integer data) {
            this.data = data;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public StackNode getNextMin() {
            return nextMin;
        }

        public void setNextMin(StackNode nextMin) {
            this.nextMin = nextMin;
        }

    }

    private LinkedList<StackNode> stack = new LinkedList<>();

    private StackNode currentMin = null;

    public void push(Integer item) {
        StackNode node = new StackNode(item);
        if (currentMin == null) {
            currentMin = node;
            node.setNextMin(null);
        } else if (item < currentMin.getData()) {
            StackNode oldMinNode = currentMin;
            node.setNextMin(oldMinNode);
            currentMin = node;
        }

        stack.addFirst(node);
    }

    public Integer pop() {
        if (stack.isEmpty()) {
            throw new EmptyStackException();
        }
        StackNode node = stack.peek();
        if (currentMin == node) {
            currentMin = node.getNextMin();
        }
        stack.removeFirst();
        return node.getData();
    }

    public Integer getMinimum() {
        if (stack.isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return currentMin.getData();
    }
}

Answer 6

To getMin elements from Stack. We have to use Two stack .i.e Stack s1 and Stack s2.

1. Initially, both stacks are empty, so add elements to both stacks

---------------------Recursively call Step 2 to 4-----------------------

2. if New element added to stack s1.Then pop elements from stack s2

3. compare new elments with s2. which one is smaller , push to s2.

4. pop from stack s2(which contains min element)

Code looks like:

package Stack;
import java.util.Stack;
public class  getMin 
{  

        Stack<Integer> s1= new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        void push(int x)
        {
            if(s1.isEmpty() || s2.isEmpty())

            {
                 s1.push(x);
                 s2.push(x);
            }
            else
            {

               s1. push(x);
                int y = (Integer) s2.pop();
                s2.push(y);
                if(x < y)
                    s2.push(x);
                        }
        }
        public Integer pop()
        {
            int x;
            x=(Integer) s1.pop();
            s2.pop();
            return x;

        }
    public  int getmin()
        {
            int x1;
            x1= (Integer)s2.pop();
            s2.push(x1);
            return x1;
        }

    public static void main(String[] args) {
        getMin s = new getMin();
            s.push(10);
            s.push(20);
            s.push(30);
            System.out.println(s.getmin());
            s.push(1);
            System.out.println(s.getmin());
        }

}