Dynamic Minimum Keeper — Problem Statement & Solution Guide

StackHardMin Stack

TimeO(1)

SpaceO(n)

Problem Description

Design a stack that supports the standard push and pop operations, along with a minKeep operation which returns the smallest element in the stack. Implement the stack such that all operations are performed in O(1) time complexity. Note: The minKeep operation should return undefined when the stack is empty.

DSA Pattern Breakdown

"Dynamic Minimum Keeper"

hard

WHY DOES IT MATTER?

This pattern is essential for problems requiring constant-time access to aggregate statistics (min, max, sum) over a dynamic collection where elements are added and removed in a specific order (LIFO). It demonstrates the ability to optimize query performance by augmenting the primary data structure with auxiliary state.

OPTIMIZATION CHALLENGE

The key insight is that the minimum element of a stack only changes when a new element is pushed that is smaller than or equal to the current minimum. By storing the minimum at each level of the stack, we eliminate the need for linear scans.

REAL-WORLD CONNECTION

This is analogous to a 'running low' tracker in inventory management. Instead of scanning all items in a warehouse to find the lowest stock level every time a new item is added or removed, the system maintains a log of the lowest stock level at each point in time, allowing instant retrieval of the current minimum.

During the interview, explicitly mention the space-time trade-off. Acknowledge that we are using O(n) extra space to achieve O(1) time, and justify this by stating that in most real-world scenarios, memory is cheaper than CPU cycles for frequent queries.

COMPLEXITY AT A GLANCE

⏱ Time:O(1)

💾 Space:O(n)

Core Theory — Why This Approach?

The 'Dynamic Minimum Keeper' problem is a classic example of trading space for time to achieve constant-time complexity for aggregate queries. A naive approach to finding the minimum element in a stack involves scanning the entire stack on every minKeep call, resulting in O(n) time complexity per query. This becomes prohibitively expensive in high-frequency trading systems or real-time monitoring dashboards where the minimum value is queried thousands of times per second. The optimal paradigm utilizes an auxiliary data structure, typically a second stack, to maintain the state of the minimum element at every depth of the primary stack.

Interview Questions on This Problem

Q1At a fintech platform, we need to track the lowest price of a stock in the last 1000 transactions. How would you design a data structure to support this with O(1) retrieval?

I would implement a MinStack using two stacks: one for the values and one for the current minimums. When pushing a value, I push the minimum of the new value and the top of the min-stack onto the min-stack. When popping, I pop from both. This ensures the top of the min-stack always holds the current minimum in O(1) time.

Q2In a distributed system, we need to track the minimum latency of requests in a sliding window. How does the MinStack pattern apply if the window size is fixed?

While MinStack is for a stack (LIFO), the core insight of maintaining a running minimum applies. For a sliding window, a deque-based monotonic queue is often better, but if the window is strictly LIFO (like a buffer), the dual-stack approach works. The key is that we store the minimum state at each step, avoiding re-computation.

Q3Why not just use a heap (priority queue) to find the minimum in O(log n) time? Why is O(1) necessary for this specific problem?

A heap provides O(log n) for extraction and O(1) for peek, but it does not support efficient removal of arbitrary elements or maintaining the stack's LIFO order for the minimum. More importantly, in high-throughput scenarios, even O(log n) can be a bottleneck. The dual-stack approach achieves true O(1) by pre-computing the minimum for every possible stack state, which is critical for latency-sensitive applications.

Examples

Example 1

Input

[48, 12, 25, 52, 10]

Output

Explanation: Step-by-step: 1. Push 48, 12, 25, 52, 10 onto the stack. The minStack is updated as [10, 12, 25, 52]. 2. Pop 48 from the stack. The minStack remains the same because 12 is still the current min. 3. The minKeep operation returns 10, which is the smallest element in the stack.

Example 2

Input

[12, 25, 52]

Output

Explanation: Step-by-step: 1. Push 12, 25, 52 onto the stack. The minStack is updated as [12, 25, 52]. 2. Pop 12 from the stack. The minStack is updated as [12 is removed, but 25 is still the current min, so 25 is removed and 52 is updated as the new min]. 3. The minKeep operation returns 12, which is the smallest element in the stack.

Constraints

The stack will contain a maximum of 1000 elements
Each element will be in the range of 1 to 10^5

Optimal Approach & Strategy

The optimal approach uses an auxiliary stack to store the minimum value at each level of the primary stack. When pushing, we compare the new value with the current minimum and push the smaller one onto the auxiliary stack; when popping, we pop from both stacks, ensuring O(1) time for all operations.

Brute Force Approach

The naive approach involves iterating through the entire stack to find the minimum element every time the minKeep operation is called. This results in O(n) time complexity for the minKeep operation, which is inefficient for large stacks.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(1)

class MinStack {
    constructor() {
        this.stack = [];
        this.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:
    stack<int> stack;
    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() {
        return stack.empty() ? -1 : stack.top();
    }

    int getMin() {
        return minStack.empty() ? -1 : minStack.top();
    }
};

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() {
        return stack.isEmpty() ? -1 : stack.peek();
    }

    public int getMin() {
        return minStack.isEmpty() ? -1 : minStack.peek();
    }
}

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):
        return self.stack[-1] if self.stack else None

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

class MinStack {
    constructor() {
        this.stack = [];
        this.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.

Dynamic Minimum Keeper Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Stack

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Dynamic Minimum Keeper — 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