min-stack.md

Requirements

Create a stack prototype with a method that returns the smallest value in constant time.

Strategy

Constructor has a push, pop, and get minimum value methods. Update the minimum value whenever we push or pop a value.

Justification of strategy

To get that sweet, sweet constant time look up for our minimum value, we have to compare the minimum value stored in our instance to any value we add, and then iterate through the stack to find a new smallest value whenever we pop.

Define test cases

• push(3), push(2), getMin() should return 2
• push(0 ... 500), getMin() should return 0
• push(-2), push(-3), push(-5), pop(), getMin() should return -3

Implementation skeleton

• create class with a minimum and stack properties.
• push method takes a value
  • add the value to the end of the stack
  • compare the value to the minimum and change the minimum if input smaller.
• pop method
  • remove the last element in the stack
  • reset the minimum
  • iterate through the stack to find the smallest value and set that as the new minimum
• get minimum method
  • just look up the minimum property

Actual implementation

https://gist.github.com/PantherHawk/402989fdb3f081c338b3be1a09f81e05

Execute test cases

function assert(a, b) {
  return a === b ? 'SUCCESS' : 'FAILURE';
}
let stack = new MinStack();
stack.push(2);
stack.push(3);
assert(stack.getMin(), 2);
stack = new MinStack();
for (var i = 0; i <= 500; i++) {
  stack.push(i);
}
assert(getMin(), 0);
stack = new MinStack();
stack.push(0);
stack.push(-3);
stack.push(-5);
stack.pop();
assert(stack.getMin(), -3);

Big-O Analysis

O(n)

Optimization (if applicable)

There's definitely room to optimize the pop method. Only change the minimum value property when the minimum value is the popped value.