Minimum Stack Tracker

Published at23 Jul 2026

Stack Medium 4 views

Like0

Design a data structure that behaves like a standard stack but also supports retrieving the minimum element in constant time. You must implement four operations:All four operations must run in O(1) time. The challenge is that the minimum changes as elements are pushed and popped, and a simple variable tracking the current minimum is insufficient because when the minimum is popped, you need to know what the previous minimum was.

The solution uses an auxiliary stack that tracks the minimum at each state. Every time you push a value, you also push the current minimum onto the auxiliary stack. When you pop, you pop from both stacks. This way, the auxiliary stack always has the minimum for the current state at its top.The challenge here is that a single variable tracking the current minimum is not enough. When the current minimum is popped, you need to know what the previous minimum was. The auxiliary stack stores exactly this history: every time you push a value, the min stack also stores the minimum at that point.An alternative approach uses a single stack storing pairs of (value, currentMin), which achieves the same result with one stack instead of two. Both approaches run in O(1) time for all operations and use O(n) space.This data structure appears in real-world interview questions and in production systems where tracking the minimum or maximum of a dynamic set is required in constant time.

Example Input & Output

Example 1

Input

push(3), push(5), getMin(), push(2), push(1), getMin(), pop(), getMin()

Output

3, 1, 2

Explanation

After pushing 3,5, min is 3. After pushing 2,1, min is 1. After popping 1, min reverts to 2.

Example 2

Input

push(-2), push(0), push(-3), getMin(), pop(), getMin()

Output

-3, -2

Explanation

Initial min is -2. After pushing -3, min becomes -3. After popping -3, min reverts to -2.

Example 3

Input

push(1), push(2), top(), getMin(), pop(), getMin()

Output

2, 1, 1

Explanation

After pushing 1 then 2, top is 2 and min is 1. After popping 2, top becomes 1 and min stays 1.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Stack Tracker

Solution Approach

The two-stack approach is the most intuitive. The main stack stores all values. The min stack stores the minimum at each step. When pushing, compare the new value with the top of the min stack and push the smaller one onto the min stack. When popping, pop from both stacks. The getMin operation simply returns the top of the min stack.

Time complexity is O(1) for all operations. Space complexity is O(n) for the two stacks combined.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
    }
    public void pop() {
        if (!stack.isEmpty()) {
            int val = stack.pop();
            if (!minStack.isEmpty() && val == minStack.peek()) minStack.pop();
        }
    }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

javascript

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
  push(val) {
    this.stack.push(val);
    if (!this.minStack.length || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }
  pop() {
    const val = this.stack.pop();
    if (this.minStack.length && val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.minStack[this.minStack.length - 1]; }
}

php

<?php
class MinStack {
    private $stack = [];
    private $minStack = [];
    function push($val) {
        array_push($this->stack, $val);
        if (empty($this->minStack) || $val <= end($this->minStack)) {
            array_push($this->minStack, $val);
        }
    }
    function pop() {
        $val = array_pop($this->stack);
        if (!empty($this->minStack) && $val === end($this->minStack)) {
            array_pop($this->minStack);
        }
    }
    function top() { return end($this->stack); }
    function getMin() { return end($this->minStack); }
}

python

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        if self.stack:
            val = self.stack.pop()
            if self.min_stack and val == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

rust

struct MinStack {
    stack: Vec<i32>,
    min_stack: Vec<i32>,
}
impl MinStack {
    fn new() -> Self { MinStack { stack: Vec::new(), min_stack: Vec::new() } }
    fn push(&mut self, val: i32) {
        self.stack.push(val);
        if self.min_stack.is_empty() || val <= *self.min_stack.last().unwrap() {
            self.min_stack.push(val);
        }
    }
    fn pop(&mut self) {
        if let Some(val) = self.stack.pop() {
            if let Some(&min_val) = self.min_stack.last() {
                if val == min_val { self.min_stack.pop(); }
            }
        }
    }
    fn top(&self) -> i32 { *self.stack.last().unwrap() }
    fn get_min(&self) -> i32 { *self.min_stack.last().unwrap() }
}

typescript

class MinStack {
    private stack: number[] = [];
    private minStack: number[] = [];
    push(val: number): void {
        this.stack.push(val);
        if (!this.minStack.length || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }
    pop(): void {
        var val = this.stack.pop();
        if (this.minStack.length && val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }
    top(): number { return this.stack[this.stack.length - 1]; }
    getMin(): number { return this.minStack[this.minStack.length - 1]; }
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Minimum Stack Tracker

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Evaluate Reverse Polish Notation

Daily Temperature Warmer

Asteroid Collision

Baseball Score Tracker

Backspace String Compare

Next Greater Element I

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.