Implement stack (push, pop and findmin) in O (1)

Question

I have already seen two stack implementations of this question, but I'm really confused how to get the operation o (1). consider the following example: S1 [3542761986759] S2 [3332221111111]

The idea / algo here is by pressing the element E on S1, check if the upper part of S2> = E is not true and if true, insert E on S2 how good it is, but when getMin is called, we return the upper part of S2, but this leaves S2 in strange state, because S2 contains repeating current minimal elements, so the solution should look for the next min element in S2 and return it. This is O9n), can someone help me understand the solution?

Answer 1

Using a linked list keeps the current minimum value. When you add a new number, it looks at the previous min and changes the current min to the current value if the current value is lower.

For example ... Suppose you have data: 3, 6, 4, 2, 7, 1. Then it will look like

value | min

3|3 -> 6|3 -> 4|3 -> 2|2 -> 7|2 -> 1|1 

This will keep track of the minutes when you click / pop items. Of course, you need to have root node and node designated as a “footer” so that you can access the end in O (1).

Or you can go back and add things to the front and change the root of the node each insert ... this will work too. It will be something like this:

 1|1 -> 7|2 -> 2|2 -> 4|3 -> 6|3 -> 3|3 

Then you don’t need the “footer” node.

Both of them will track the current value of min when the value has been pressed. Thus, when the current value of min is pressed, he will know what the second value of min was in O (1).

Answer 2

It's impossible. Otherwise, you can implement the sorting of comparisons in linear time: first click all the elements in O (1) each, O (n) the total time, and then n times get the minimum in O (n) the total time.

As you know, O (n log n) is the lower bound for sorting comparisons; a solution with O (1) push and findmin cannot exist.

Edit: Replace "sort" with "sort sort", as Gabe noted.

Answer 3

I post the full code here to find min and mx on the stack. The complexity of time will be equal to O (1)

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

/ ** * * @author vsinha * * / open abstract Stack interface {

 /** * 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") MinMaxStack public abstract interface expands stack {

 public abstract int min(); public abstract int max(); 

}

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

import java.util.Arrays;

/ ** * * @author vsinha * * @param * / The public class MyStack implements Stack {

 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;

/ ** * The complexity of the time will be O (1) to find the min and max in the given stack. * @author vsinha * * / Public class MinMaxStackFinder extends MyStack implements MinMaxStack {

 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 + "]" ; } 

}

// Testing program

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

}

Exit:

MyStack [elements = [99, 76, 92, 49, 89, 88, 93, 33, 0, 30], size = 10, top = 9] MinMaxStackFinder [minStack = MyStack [elements = [99, 76, 49, 33 , 0, null, null, null, null, null], size = 5, top = 4] maxStack = MyStack [elements = [99, null, null, null, null, null, null, null, null, null], size = 1, top = 0]] MAX: 99 MIN: 0 MyStack [elements = [99, 76, 92, 49, 89, null, null, null, null, null], size = 5, top = 4] MinMaxStackFinder [minStack = MyStack [elements = [99, 76, 49, null, null, null, null, null, null, null], size = 3, top = 2] maxStack = MyStack [elements = [99, null, null, null, null, null, null, null, null, null], size = 1, top = 0]] MAX: 99 MIN: 49

Let me know if you have any problems.

Thank you, VIKASH SINHA