Design a stack with push, pop, and min operations in constant time.

A stack is a data structure that supports push, pop, and min operations in constant time.

Problem

Design a stack that supports push, pop, and min operations in constant time.
Example input:
push(5), push(3), push(7), push(2), min()
Example output:
2

Solution

This solution is in JavaScript. Our A.I. can create solutions in multiple languages.
by kayakane
// Solution:
// The solution is to use a second stack to keep track of the minimum value.
// When a new value is pushed onto the stack, it is also pushed onto the min stack if it is less than or equal to the current min value.
// When a value is popped off the stack, it is also popped off the min stack if it is equal to the current min value.
// This way, the min stack will always have the current min value at the top.
// This solution is optimal because it allows for constant time min operations.

class Stack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }

  push(value) {
    this.stack.push(value);
    if (this.minStack.length === 0 || value <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(value);
    }
  }

  pop() {
    const value = this.stack.pop();
    if (value === this.minStack[this.minStack.length - 1]) {
      this.minStack. pop();
    }
    return value;
  }

  min() {
    return this.minStack[this.minStack.length - 1];
  }
}

const stack = new Stack();
stack.push(5);
stack.push(3);
stack.push(7);
stack.push(2);
console.log(stack.min()); // 2
stack.pop();
console.log(stack.min()); // 3
stack.pop();
console.log(stack.min()); // 3
stack.pop();
console.log(stack.min()); // 5
stack.pop();
console.log(stack.min()); // undefined

A.I. Evaluation of the Solution

The candidate's solution is complete and solves the problem. The candidate's approach is to use a second stack to keep track of the minimum value. When a new value is pushed onto the stack, it is also pushed onto the min stack if it is less than or equal to the current min value. When a value is popped off the stack, it is also popped off the min stack if it is equal to the current min value. This way, the min stack will always have the current min value at the top. This solution is optimal because it allows for constant time min operations.

Evaluated at: 2022-12-04 08:15:41