Efficient Minimum Value Tracker — Problem Statement & Solution Guide

DesignHardMin Stack

TimeO(1)

SpaceO(n)

Problem Description

Design a class MinTracker that maintains a sequence of numerical values supporting four core operations: push(val), pop(), top(), and getMin(). The push operation appends a value to the end of the sequence, pop removes the most recently added value, top returns the current last value without removing it, and getMin returns the smallest value currently present in the sequence. All operations must execute in O(1) amortized time complexity. The system must correctly handle edge cases including an empty sequence, negative integers, and floating-point values such as Infinity and -Infinity. If pop, top, or getMin is called on an empty sequence, the method should return null or throw a specific EmptyTrackerError as defined by the implementation context.

DSA Pattern Breakdown

"Efficient Minimum Value Tracker"

hard

WHY DOES IT MATTER?

The pattern of augmenting a stack with auxiliary state (min, max, frequency) is fundamental because many real‑world problems need fast aggregate queries on a dynamic dataset, and stacks provide a natural LIFO ordering for such scenarios.

OPTIMIZATION CHALLENGE

The key insight is to store the current minimum alongside each element, turning a potentially O(n) scan into a constant‑time peek by preserving historical minima as the stack evolves.

REAL-WORLD CONNECTION

Think of a warehouse inventory where items are stacked; the auxiliary stack is like a side ledger that records the lightest package at each level, allowing instant lookup without moving the whole pile.

During an interview, push the auxiliary‑stack idea early; even if you later switch to the encoded‑value trick, demonstrating awareness of the two‑stack solution shows solid problem‑solving depth.

COMPLEXITY AT A GLANCE

⏱ Time:O(1)

💾 Space:O(n)

Core Theory — Why This Approach?

The MinTracker problem is a classic example of augmenting a stack to support an additional query—retrieving the minimum element—in constant time. A naïve implementation would scan the entire stack on each getMin call, yielding O(n) time per query, which quickly becomes a bottleneck for large sequences or high‑frequency operations. The optimal paradigm leverages auxiliary information stored alongside each element, typically by maintaining a secondary stack that mirrors the primary one but records the current minimum at each depth. This way, push, pop, top, and getMin all operate in O(1) time because the minimum for the current state is always at the top of the auxiliary stack.

The underlying theory draws from the concept of *persistent state* in data structures: each operation updates a snapshot of the structure without recomputing from scratch. By coupling each pushed value with the minimum seen so far, we create a monotonic decreasing sequence in the auxiliary stack, ensuring that pop operations correctly revert the minimum to the previous state. This approach also respects space efficiency, using O(n) extra space—linear in the number of elements—while guaranteeing worst‑case constant‑time performance for all supported operations.

Interview Questions on This Problem

Q1How would you modify the MinTracker to also support retrieving the maximum element in O(1) time?

Maintain a second auxiliary stack that tracks the current maximum alongside the minimum stack. On push, push the new value onto the max stack if it is greater than or equal to the current top; on pop, pop from both auxiliary stacks if the popped value matches their tops. This preserves O(1) getMax.

Q2Can you implement MinTracker using only one stack without extra space beyond O(1)?

Yes, by encoding the previous minimum within the stored values using a mathematical trick (e.g., storing 2*val - min when val < min). On push/pop, decode the previous minimum accordingly. This achieves O(1) time and O(1) extra space beyond the primary stack.

Q3Why is a simple linear scan for getMin unacceptable in a real‑time trading system?

Trading systems require sub‑millisecond latency; a linear scan introduces O(n) latency that grows with the number of open orders, leading to unpredictable delays and potential SLA violations. Constant‑time retrieval guarantees deterministic performance regardless of load.

Examples

Example 1

Input

tracker = MinTracker()
tracker.push(15)
tracker.push(3)
tracker.push(7)
tracker.getMin()
tracker.pop()
tracker.getMin()
tracker.top()

Output

3, 3, 7

Explanation: 1. Push 15: Sequence is [15], min is 15. 2. Push 3: Sequence is [15, 3], min is 3. 3. Push 7: Sequence is [15, 3, 7], min is 3. 4. getMin() returns 3. 5. pop() removes 7: Sequence is [15, 3], min remains 3. 6. getMin() returns 3. 7. top() returns 3.

Example 2

Input

tracker = MinTracker()
tracker.push(-10)
tracker.push(5)
tracker.push(-20)
tracker.getMin()
tracker.pop()
tracker.getMin()
tracker.pop()
tracker.getMin()

Output

-20, -10, -10

Explanation: 1. Push -10: Sequence is [-10], min is -10. 2. Push 5: Sequence is [-10, 5], min is -10. 3. Push -20: Sequence is [-10, 5, -20], min is -20. 4. getMin() returns -20. 5. pop() removes -20: Sequence is [-10, 5], min reverts to -10. 6. getMin() returns -10. 7. pop() removes 5: Sequence is [-10], min is -10. 8. getMin() returns -10.

Example 3

Input

tracker = MinTracker()
tracker.push(Infinity)
tracker.push(42)
tracker.getMin()
tracker.pop()
tracker.getMin()
tracker.pop()
tracker.getMin()

Output

42, Infinity, null

Explanation: 1. Push Infinity: Sequence is [Infinity], min is Infinity. 2. Push 42: Sequence is [Infinity, 42], min is 42. 3. getMin() returns 42. 4. pop() removes 42: Sequence is [Infinity], min is Infinity. 5. getMin() returns Infinity. 6. pop() removes Infinity: Sequence is empty. 7. getMin() returns null (or throws EmptyTrackerError).

Example 4

Input

tracker = MinTracker()
tracker.push(100)
tracker.push(100)
tracker.push(100)
tracker.getMin()
tracker.pop()
tracker.getMin()
tracker.pop()
tracker.getMin()
tracker.pop()
tracker.getMin()

Output

100, 100, 100, null

Explanation: 1. Push 100: Sequence is [100], min is 100. 2. Push 100: Sequence is [100, 100], min is 100. 3. Push 100: Sequence is [100, 100, 100], min is 100. 4. getMin() returns 100. 5. pop() removes last 100: Sequence is [100, 100], min is 100. 6. getMin() returns 100. 7. pop() removes last 100: Sequence is [100], min is 100. 8. getMin() returns 100. 9. pop() removes last 100: Sequence is empty. 10. getMin() returns null.

Constraints

1 <= number of operations <= 10^5
-10^9 <= val <= 10^9 for integer inputs
val can be Infinity, -Infinity, or NaN (implementation must define behavior for NaN, typically treating it as greater than all numbers or throwing an error)
All operations must complete in O(1) time complexity
Memory usage must be O(n) where n is the maximum size of the tracker at any point

Optimal Approach & Strategy

Maintain an auxiliary min‑stack that records the minimum at each push, allowing getMin to return the top of this stack in O(1) time, while push and pop update both stacks in constant time.

Brute Force Approach

Store values in a plain stack and, on each getMin call, scan the entire stack to find the smallest element, resulting in O(n) time per query.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(1)

class MinStack {
  stack = [];
  minStack = [];

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

  pop() {
    if (this.stack.length > 0) {
      const x = this.stack.pop();
      if (x === this.minStack[this.minStack.length - 1])
        this.minStack.pop();
      return x;
    }
    return null;
  }

  top() {
    if (this.stack.length > 0)
      return this.stack[this.stack.length - 1];
    return null;
  }

  getMin() {
    if (this.minStack.length > 0)
      return this.minStack[this.minStack.length - 1];
    return null;
  }
}

class MinStack {
public:
  std::stack<int> stack;
  std::stack<int> minStack;

  void push(int x) {
    stack.push(x);
    if (minStack.empty() || x <= minStack.top())
      minStack.push(x);
  }

  int pop() {
    if (!stack.empty()) {
      int x = stack.top();
      stack.pop();
      if (x == minStack.top())
        minStack.pop();
      return x;
    }
    return -1;
  }

  int top() {
    if (!stack.empty())
      return stack.top();
    return -1;
  }

  int getMin() {
    if (!minStack.empty())
      return minStack.top();
    return -1;
  }
};

class MinStack {
  private Stack<Integer> stack = new Stack<>();
  private Stack<Integer> minStack = new Stack<>();

  public void push(int x) {
    stack.push(x);
    if (minStack.isEmpty() || x <= minStack.peek())
      minStack.push(x);
  }

  public int pop() {
    if (!stack.isEmpty()) {
      int x = stack.pop();
      if (x == minStack.peek())
        minStack.pop();
      return x;
    }
    return -1;
  }

  public int top() {
    if (!stack.isEmpty())
      return stack.peek();
    return -1;
  }

  public int getMin() {
    if (!minStack.isEmpty())
      return minStack.peek();
    return -1;
  }
}

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

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

  def pop(self):
    if self.stack:
      x = self.stack.pop()
      if x == self.minStack[-1]:
        self.minStack.pop()
      return x
    return None

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

  def getMin(self):
    if self.minStack:
      return self.minStack[-1]
    return None

class MinStack {
  stack = [];
  minStack = [];

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

  pop() {
    if (this.stack.length > 0) {
      const x = this.stack.pop();
      if (x === this.minStack[this.minStack.length - 1])
        this.minStack.pop();
      return x;
    }
    return null;
  }

  top() {
    if (this.stack.length > 0)
      return this.stack[this.stack.length - 1];
    return null;
  }

  getMin() {
    if (this.minStack.length > 0)
      return this.minStack[this.minStack.length - 1];
    return null;
  }
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Efficient Minimum Value Tracker Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Design

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Efficient Minimum Value Tracker — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor