Minimum Value Tracker — Problem Statement & Solution Guide

MathMediumMin Stack

TimeO(1) per operation

SpaceO(n)

Problem Description

Design a data structure that supports push, pop, and retrieveMin operations. The push operation adds an element to the top of the stack, the pop operation removes the top element from the stack, and the retrieveMin operation returns the minimum element currently in the stack.

DSA Pattern Breakdown

"Minimum Value Tracker"

medium

WHY DOES IT MATTER?

The min-stack pattern is essential because it transforms a linear-time query into a constant-time operation, which is critical for performance-sensitive applications like financial tickers or real-time gaming. It also illustrates how auxiliary data structures can be leveraged to maintain invariants without compromising the primary structure's simplicity.

OPTIMIZATION CHALLENGE

The key insight is to store the minimum value alongside each element in the stack, rather than recomputing it. By pushing the current minimum onto a parallel stack, we avoid scanning the entire stack on each getMin call.

REAL-WORLD CONNECTION

Consider a stock trading platform that needs to report the lowest price in a sliding window of trades. Maintaining a min-stack allows the system to update the minimum in real time as trades are added or removed, similar to how a min-heap is used in priority queues for scheduling tasks.

When explaining this pattern in an interview, emphasize the invariant that the min-stack's top always equals the minimum of the main stack. Demonstrate the push/pop logic with a small example to show how the invariant is preserved.

COMPLEXITY AT A GLANCE

⏱ Time:O(1) per operation

💾 Space:O(n)

Core Theory — Why This Approach?

The Minimum Value Tracker problem is a classic example of augmenting a simple data structure to support an additional query in constant time. A naive stack implementation can push and pop in O(1), but retrieving the minimum requires scanning the entire stack, leading to O(n) time per query. This linear scan becomes a bottleneck when the stack contains millions of elements or when the operation is called frequently.

The optimal solution introduces a second stack (often called the min-stack) that mirrors the main stack but stores the current minimum at each level. When pushing a new element, we compare it with the top of the min-stack; if it is smaller or equal, we push it onto the min-stack as well. When popping, we simultaneously pop from both stacks if the popped element equals the current minimum. This guarantees that the top of the min-stack always holds the minimum of the remaining elements, allowing retrieveMin to run in O(1) time.

This pattern exemplifies the principle of *lazy augmentation*: we store just enough auxiliary information to answer the query efficiently without recomputing from scratch. It also demonstrates how a simple stack can be extended to support more complex operations while preserving its core properties, a technique that appears in many interview questions and real-world systems.

Interview Questions on This Problem

Q1How would you modify a standard stack to support a getMin() operation in O(1) time and O(n) space?

Use an auxiliary stack that keeps track of the minimum value at each push. Push the new element onto the main stack; if the min-stack is empty or the new element is <= the current min, push it onto the min-stack as well. For pop, pop from the main stack and if the popped value equals the top of the min-stack, pop from the min-stack too. getMin() simply returns the top of the min-stack.

Q2In a distributed system, why might you prefer a min-stack over recomputing the minimum after each update?

Recomputing the minimum would require scanning potentially large datasets or aggregating across nodes, incurring high latency and network overhead. A min-stack provides constant-time updates and queries, enabling low-latency services such as real-time analytics or monitoring dashboards.

Q3What edge cases should you handle when implementing the min-stack in a production codebase?

Handle duplicate minimum values correctly by pushing duplicates onto the min-stack; ensure that pop operations synchronize both stacks; and guard against underflow by checking that the stack is not empty before pop or getMin.

Examples

Example 1

Input

[10, 15, 10, 5, 20, 15]

Output

[10, 15, 10, null, 5, 15]

Explanation: Step 1: Push 10 onto the stack, minStack remains empty. Stack: [10], minStack: [] Step 2: Push 15 onto the stack, minStack is updated with 10. Stack: [10, 15], minStack: [10] Step 3: Push 10 onto the stack, minStack is updated with 10. Stack: [10, 15, 10], minStack: [10, 10] Step 4: Push 5 onto the stack, minStack is updated with 5. Stack: [10, 15, 10, 5], minStack: [10, 10, 5] Step 5: Pop 5 from the stack, minStack is updated to remove 5. Stack: [10, 15, 10], minStack: [10, 10] Step 6: Pop 10 from the stack, minStack is updated to remove 10. Stack: [10, 15], minStack: [10] Step 7: Pop 15 from the stack, minStack is updated to remove 10. Stack: [10], minStack: [] Step 8: Pop 10 from the stack, minStack is updated to remove 10. Stack: [], minStack: []

Example 2

Input

[50, 40, 30, 20, 10]

Output

[50, 40, 30, 20, 10]

Explanation: Step 1: Push 50 onto the stack, minStack remains empty. Stack: [50], minStack: [] Step 2: Push 40 onto the stack, minStack is updated with 40. Stack: [50, 40], minStack: [40] Step 3: Push 30 onto the stack, minStack is updated with 30. Stack: [50, 40, 30], minStack: [30, 40] Step 4: Push 20 onto the stack, minStack is updated with 20. Stack: [50, 40, 30, 20], minStack: [20, 30, 40] Step 5: Push 10 onto the stack, minStack is updated with 10. Stack: [50, 40, 30, 20, 10], minStack: [10, 20, 30, 40]

Constraints

All push and pop operations are valid (i.e., pop will not be called on an empty stack).
The input stream will contain a mix of positive integers and -1, where -1 indicates a pop operation.

Optimal Approach & Strategy

Maintain a second stack that stores the current minimum at each push. All operations—push, pop, and retrieveMin—run in O(1) time, with O(n) auxiliary space.

Brute Force Approach

Push and pop operate in O(1), but retrieveMin scans the entire stack, resulting in O(n) time per query. This approach quickly becomes impractical for large stacks or frequent min queries.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(1) per operation

function MinStack() {
   this.stack = [];
   this.minStack = [];
}

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

MinStack.prototype.pop = function() {
   if (this.stack.length > 0) {
       let top = this.stack.pop();
       if (top === this.minStack[this.minStack.length - 1]) {
           this.minStack.pop();
       }
       return top;
   }
   return null;
}

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

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

class MinStack {
public:
   MinStack() {
       stack = new std::stack<int>();
       minStack = new std::stack<int>();
   }

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

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

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

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

private:
   std::stack<int> *stack;
   std::stack<int> *minStack;
};

class MinStack {
   private Stack<Integer> stack;
   private Stack<Integer> minStack;

   public MinStack() {
       stack = new Stack<>();
       minStack = new Stack<>();
   }

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

   public Integer pop() {
       if (!stack.isEmpty()) {
           int top = stack.pop();
           if (top == minStack.peek()) {
               minStack.pop();
           }
           return top;
       }
       return null;
   }

   public Integer top() {
       if (!stack.isEmpty()) {
           return stack.peek();
       }
       return null;
   }

   public Integer getMin() {
       if (!minStack.isEmpty()) {
           return minStack.peek();
       }
       return null;
   }
}

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:
           top = self.stack.pop()
           if top == self.minStack[-1]:
               self.minStack.pop()
           return top
       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

function MinStack() {
   this.stack = [];
   this.minStack = [];
}

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

MinStack.prototype.pop = function() {
   if (this.stack.length > 0) {
       let top = this.stack.pop();
       if (top === this.minStack[this.minStack.length - 1]) {
           this.minStack.pop();
       }
       return top;
   }
   return null;
}

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

MinStack.prototype.getMin = function() {
   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.

Minimum Value Tracker Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Math

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

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