Coding problem · Medium · Stack

Min Stack

Medium Algorithms & data structures Seen at Amazon, Bloomberg, Microsoft

Design a stack that supports push, pop, top and retrieving the minimum element — all in O(1) time.

push(val) pushes val.
pop() removes the top element.
top() returns the top element.
getMin() returns the minimum element in the stack.

pop, top and getMin are only called on non-empty stacks.

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]

Hints

Hint 1

Store, alongside each value, the minimum of the stack at the time it was pushed.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(1) per operation · Space O(n)

Push pairs (value, minSoFar) where minSoFar = min(value, previous pair's min). The top pair always holds the current minimum, and popping restores the previous minimum automatically.

Reference solution

class MinStack {
  constructor() {
    this.items = []; // [value, minSoFar]
  }
  push(val) {
    const min = this.items.length ? Math.min(val, this.items[this.items.length - 1][1]) : val;
    this.items.push([val, min]);
  }
  pop() {
    this.items.pop();
  }
  top() {
    return this.items[this.items.length - 1][0];
  }
  getMin() {
    return this.items[this.items.length - 1][1];
  }
}

class MinStack {
  private items: [number, number][] = [];

  push(val: number): void {
    const min = this.items.length ? Math.min(val, this.items[this.items.length - 1][1]) : val;
    this.items.push([val, min]);
  }

  pop(): void {
    this.items.pop();
  }

  top(): number {
    return this.items[this.items.length - 1][0];
  }

  getMin(): number {
    return this.items[this.items.length - 1][1];
  }
}

class MinStack:
    def __init__(self):
        self.items: list[tuple[int, int]] = []

    def push(self, val: int) -> None:
        low = min(val, self.items[-1][1]) if self.items else val
        self.items.append((val, low))

    def pop(self) -> None:
        self.items.pop()

    def top(self) -> int:
        return self.items[-1][0]

    def get_min(self) -> int:
        return self.items[-1][1]

<?php

class MinStack
{
    private array $items = [];

    public function push(int $val): void
    {
        $min = $this->items ? min($val, end($this->items)[1]) : $val;
        $this->items[] = [$val, $min];
    }

    public function pop(): void
    {
        array_pop($this->items);
    }

    public function top(): int
    {
        return end($this->items)[0];
    }

    public function getMin(): int
    {
        return end($this->items)[1];
    }
}

class MinStack {
    private final Deque<int[]> items = new ArrayDeque<>();

    public MinStack() {}

    public void push(int val) {
        int min = items.isEmpty() ? val : Math.min(val, items.peek()[1]);
        items.push(new int[]{val, min});
    }

    public void pop() { items.pop(); }

    public int top() { return items.peek()[0]; }

    public int getMin() { return items.peek()[1]; }
}

Common mistakes

Keeping a single min variable — you can't recover the previous minimum after popping it.

Valid Parentheses · Easy
Daily Temperatures · Medium