Thursday, 27 April 2017

Design a stack that supports getMinimum() in O(1) time

Problem statement:
Find the minimum element in a stack in O(1) time complexity and O(n) space complexity

Solution:
Maintain another stack and keep pushing the minimum element on the stack as in when found.
Before each push on stack 1, just check if the current element is less than the top element of the second stack if yes then push it on to stack 2.

While popping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next minimum would show up on stack 2 for next min operation.

Inserts an element e1 to Stack.
push(int e1)
1) push e1 to the stack 1.
2) compare e1 with the top element(=e2) of the stack 2 (the auxiliary stack).
   a) If e1<e2, then push e1 to the auxiliary stack.
   b) If e1>e2, then push e2 to the auxiliary stack.

Removes an element from Stack and return the removed element.
int pop()
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

Returns the minimum element from Stack.
int getMinimum()
1) Return the top element of the auxiliary stack.

This would ensure that we pop out the minimum element in O(1) time.

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...