Min Stack

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Medium

Approach 1

Level I: Brute Force (Scan on getMin)

Intuition

Maintain a simple stack of elements. Every time getMin() is called, iterate through the entire stack to find the minimum element.

⏱ Push/Pop: O(1), getMin: O(N).💾 O(N).

Detailed Dry Run

Push(5), Push(3), getMin() -> Scan [5, 3] -> Min is 3.

java

class MinStack {
    private Stack<Integer> s = new Stack<>();
    public void push(int x) { s.push(x); }
    public void pop() { s.pop(); }
    public int top() { return s.peek(); }
    public int getMin() {
        int min = Integer.MAX_VALUE;
        for(int x : s) min = Math.min(min, x);
        return min;
    }
}

Approach 2

Level II: Two Stacks (Standard Optimality)

Intuition

Maintain a second stack to store the minimum value encountered so far for each element in the main stack. This ensures getMin() is $O(1)$ .

⏱ O(1) all ops.💾 O(N).

Detailed Dry Run

Push(5), Push(3) | Stack | MinStack | Action | | :--- | :--- | :--- | :--- | | [5] | [5] | | | [5, 3] | [5, 3] | 3 < 5, so push 3 | | pop() | [5] | both pop |

java

import java.util.*;
class MinStack {
    private Stack<Integer> s = new Stack<>(), min = new Stack<>();
    public void push(int x) { s.push(x); if(min.isEmpty() || x <= min.peek()) min.push(x); }
    public void pop() { if(s.pop().equals(min.peek())) min.pop(); }
    public int top() { return s.peek(); }
    public int getMin() { return min.peek(); }
}

Approach 3

Level III: Optimized Space (Single Stack with Min Delta)

Intuition

Store only the difference between the current value and the minimum value. This allows us to reconstruct the previous minimum when the current minimum is popped.

⏱ O(1) all ops.💾 O(1) auxiliary (excluding stack).

Detailed Dry Run

Push(x): store (x - min). If x < min, update min = x.

java

import java.util.*;\nclass MinStack {\n    private Stack<Long> s = new Stack<>();\n    private long min;\n    public void push(int val) {\n        if(s.isEmpty()) { s.push(0L); min = val; }\n        else { s.push(val - min); if(val < min) min = val; }\n    }\n    public void pop() {\n        long diff = s.pop();\n        if(diff < 0) min = min - diff;\n    }\n    public int top() {\n        long diff = s.peek();\n        return diff > 0 ? (int)(diff + min) : (int)min;\n    }\n    public int getMin() { return (int)min; }\n}

← Previous QuestionDesign Circular Queue

Next Question →Design Add and Search Words

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.