Skip to content

Instantly share code, notes, and snippets.

@abinavseelan
Created May 2, 2018 15:58
Show Gist options
  • Save abinavseelan/823d920a635e4602a5e30272ca53be7a to your computer and use it in GitHub Desktop.
Save abinavseelan/823d920a635e4602a5e30272ca53be7a to your computer and use it in GitHub Desktop.
Build an implementation of a stack in JS. The smallest value in the stack should be retrieveable in O(1)
function Stack() {
this.min = Infinity;
this.values = [];
}
Stack.prototype.push = function(value) {
this.values[this.values.length] = value; // Using this logic since .push() was banned from use.
if (value < this.min) {
this.min = value;
}
}
Stack.prototype.pop = function(value) {
const poppedValue = this.values[this.values.length - 1];
this.values.splice(this.values.length - 1, 1); // Remove the last item
if (poppedValue === this.min) {
// If the value that was popped is the min, then find the min of the remaining values.
this.min = Infinity;
this.values.forEach(v => {
if (v < this.min) {
this.min = v;
}
});
}
return poppedValue;
}
Stack.prototype.getMin = function() {
return this.min;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment