Stack with function min in O(1) time

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

My initial thoughts:
We can keep an record of the current minimum element and dynamically update it when doing the push. However, the update cannot be kept when poping. Therefore I can only implement a O(1) push(), min() but O(n) pop() data structure.

My initial codes:

public class Q3_2 {

	private StackNode<Integer> top = null;
	private Integer min = Integer.MAX_VALUE;

	public void push(Integer item) {
		StackNode<Integer> t = new StackNode<Integer>(item);
		t.setUnderneath(top);
		top = t;

		if (item < min)
			min = item;
	}

	public Integer pop() {
		if (top == null)
			return null;
		Integer data = top.getData();
		top = top.getUnderneath();

		if (data == min) {
			min = Integer.MAX_VALUE;
			StackNode<Integer> curr = top;
			while (curr != null) {
				if (curr.getData() < min)
					min = curr.getData();
				curr = curr.getUnderneath();
			}
		}

		return data;
	}

	public Integer min() {
		return min;
	}
}

Solution:

public class StackWithMinNode<T> extends StackNode<T> {

	private Integer min = null;
	private StackWithMinNode<T> underneath = null;

	public StackWithMinNode(T item) {
		super(item);
	}

	public Integer min() {
		return min;
	}

	public void setMin(Integer min) {
		this.min = min;
	}

	@Override
	public StackWithMinNode<T> getUnderneath() {
		return underneath;
	}

	public void setUnderneath(StackWithMinNode<T> underneath) {
		this.underneath = underneath;
	}

}

public class StackWithMin extends MyStack<Integer> {

	StackWithMinNode<Integer> top = null;

	@Override
	public void push(Integer data) {
		StackWithMinNode<Integer> item = 
				new StackWithMinNode<Integer>(data);
		if (top != null)
			item.setMin(Math.min(data, top.min()));
		else
			item.setMin(data);
		item.setUnderneath(top);
		top = item;
	}

	@Override
	public Integer pop() {
		if (top == null)
			return null;
		Integer data = top.getData();
		top = top.getUnderneath();
		return data;
	}

	public Integer min() {
		if (top == null)
			return null;
		return top.min();
	}
}

Comments:
The idea is similar as my initial thought, only that we keep a local minimum for each node.
Another solution is implemented using an auxiliary stack to keep track of the local minimum, therefore potentially saving spaces taken by keep track local min for each single node.

public class StackWithMinStack extends MyStack<Integer> {

	MyStack<Integer> minStack = new MyStack<Integer>();

	@Override
	public void push(Integer data) {
		StackNode<Integer> item = new StackNode<Integer>(data);
		if (minStack.isEmpty())
			minStack.push(data);
		else {
			if (data.compareTo(minStack.peek()) <= 0)
				minStack.push(data);
		}
		item.setUnderneath(top);
		top = item;
	}

	@Override
	public Integer pop() {
		if (top == null)
			return null;
		Integer data = top.getData();
		if (data.compareTo(minStack.peek()) == 0)
			minStack.pop();
		top = top.getUnderneath();
		return data;
	}

	public Integer min() {
		if (minStack.isEmpty())
			return null;
		return minStack.peek();
	}
}

Comment: Be careful about line 11. We push into the auxiliary stack if we have found element less OR equal to the local min. We have to keep duplicates in order to further deal with the case where one duplicate is poped. Think about this stack from top to bottom (on the right is its auxiliary stack, storing the local min):
5
2
4 2
2 2
7 7
If we only store one 2 in the auxiliary stack, then when 5 and 2 are poped from the original stack, the auxiliary stack will only be left with 7, resulting in a wrong global min.

Advertisements

2 Comments (+add yours?)

  1. Trackback: Idea Board | CtCI 3.2
  2. cracking the coding interview
    Oct 28, 2013 @ 06:18:01

    Good day! I know this is kinda off topic but I was wondering
    which blog platform are you using for this website? I’m getting sick
    and tired of WordPress because I’ve had problems with
    hackers and I’m looking at options for another platform.

    I would be great if you could point me in the direction of a good platform.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: