The Forum > Front Page Posts > Coding Interview 6: Constant Time Stack with GetMin
"Create a datastructure that is a stack with Push, Pop commands that work in constant time. Additionally, there should be another command called GetMin which returns the smallest element in the stack." If you have a collection of things, and you want to find the smallest element in it, you have to iterate through the collection to find it. Generally. This may give you the impression that Push and Pop are O(1) operations and GetMin is O(n). However there are better ways than brute force. Because this collection is limited to two specific operations that you can implement any way you want, the first reaction is to keep track of a minimum and update it when you push a number larger than the minimum. This is a O(1) operation. However, popping a number that's a minimum will require you to go through the collection and re-calculate the new minimum. The simple implementation is O(n) but only in cases when the minimum is popped. All other cases are O(1) as well. This is a good solution for most cases, and can be optimized to O(log n) if you try hard enough. But the question deals with a stack. The stack has a unique quality that any state of the stack can be tracked alongside the element in the stack. Imagine an implementation where you store tuple'd pairs in the stack instead of just integers. The first number in the tuple is the number you're pushing into the stack. The 2nd number is the minimum of the stack when that number was pushed. Once you pop a tuple, you're left with an accurate min at the new top of the stack. struct stack_node: function constructor(num, min): this->num = num this->min = min class special_stack: function constructor(): this->stack = new stack() function get_min(): item = this->stack->top_item() // does not pop return item->min function pop(): item = this->stack->pop() return item->num function push(num): min = num if this->list->length > 0: if this->get_min() < num: min = this->get_min() item = new stack_node(num, min) this->list->push(item) Imagine pushing the following numbers onto this special stack: 3, 4, 2, 5, 1 Start with the 3. The stack will look like this (imagine the top of the stack is the first line): (num: 3, min: 3) Push the 4: (num: 4, min: 3) (num: 3, min: 3) Because 4 is greater than the min of the top of the stack, we push the min with the num. If you were to call get_min at this point, you would get a 3. If you were to pop the 4, then get_min would still return a 3. Push the 2: (num: 2, min: 2) (num: 4, min: 3) (num: 3, min: 3) Now that we've pushed a number that is smaller than the min, we push it with itself as the min. Push the 1: (num: 1, min: 1) (num: 2, min: 2) (num: 4, min: 3) (num: 3, min: 3) And the 5: (num: 5, min: 1) (num: 1, min: 1) (num: 2, min: 2) (num: 4, min: 3) (num: 3, min: 3) Popping numbers in this stack will always reveal the accurate state of the stack at the time the number was pushed because there is no other way to modify a traditional stack data-structure except pushing and popping. |
![[avatar]](/uploads/avatars/1_871929099.png)
The Forum > Front Page Posts > Coding Interview 6: Constant Time Stack with GetMin