Interview Prepstacks-monotonic-stackmediumAmazonGoogleFacebookBloomberg

Minimum Stack (Min in O(1))

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine a stack of plates where you want to quickly know the smallest plate at any time without sorting or scanning all plates.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the following operations: push(x) - Push element x onto stack; pop() - Removes the element on top of the stack; top() - Get the top element; getMin() - Retrieve the minimum element in the stack.

1 ≤ number of operations ≤ 10^5-10^9 ≤ x ≤ 10^9pop, top, and getMin operations will always be called on non-empty stacks

Edge cases: Only one element pushed → getMin returns that elementAll elements pushed are the same → getMin returns that elementStrictly increasing elements pushed → getMin returns the first pushed element

</>

IDE

class MinStack:
    def __init__(self):
        pass
    def push(self, x: int) -> None:
        pass
    def pop(self) -> None:
        pass
    def top(self) -> int:
        pass
    def getMin(self) -> int:
        pass

class MinStack:
    def __init__(self):
        # Write your solution here
        pass
    def push(self, x: int) -> None:
        pass
    def pop(self) -> None:
        pass
    def top(self) -> int:
        pass
    def getMin(self) -> int:
        pass

class MinStack {
    public MinStack() {
        // Write your solution here
    }
    public void push(int x) {
    }
    public void pop() {
    }
    public int top() {
        return 0;
    }
    public int getMin() {
        return 0;
    }
}

#include <vector>
using namespace std;

class MinStack {
public:
    MinStack() {
        // Write your solution here
    }
    void push(int x) {
    }
    void pop() {
    }
    int top() {
        return 0;
    }
    int getMin() {
        return 0;
    }
};

class MinStack {
    constructor() {
        // Write your solution here
    }
    push(x) {
    }
    pop() {
    }
    top() {
        return null;
    }
    getMin() {
        return null;
    }
}

0/9

Common Bugs to Avoid

Wrong: getMin returns wrong minimum after popNot popping from auxiliary min stack when popping main stack✅ Pop from min stack in pop() method whenever popping main stack

Wrong: getMin returns incorrect value with duplicate minimumsNot pushing duplicates of minimum value onto min stack✅ Push min(minStack.top(), x) on every push, even if equal

Wrong: getMin returns wrong after popping all elements and pushing newMin stack not reset after emptying main stack✅ Initialize min stack on first push after empty stack

Wrong: TLE on large inputgetMin implemented by scanning entire stack each time✅ Maintain auxiliary min stack to get min in O(1)

✓

Test Cases

t1_01basic

Input["push(-2)","push(0)","push(-3)","getMin()","pop()","top()","getMin()"]

Expected[null,null,null,-3,null,0,-2]

After pushing -2, 0, -3, the minimum is -3. After popping -3, top is 0 and minimum is -2.

t1_02basic

Input["push(1)","push(2)","push(-1)","getMin()","pop()","getMin()","top()"]

Expected[null,null,null,-1,null,1,1]

Minimum after pushing 1,2,-1 is -1. After popping -1, minimum is 1 and top is 1.

Practice

(1/5)

1. You need to implement a fixed-size data structure that supports enqueue and dequeue operations in O(1) time, and efficiently reuses space when elements are removed. Which approach best guarantees these requirements?

easy

A. Use a stack and reverse it on each dequeue operation.

B. Use a dynamic array and shift elements on dequeue to maintain order.

C. Use a linked list with pointers to head and tail nodes.

D. Use a fixed-size array with head and tail pointers and a size variable to distinguish full and empty states.

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Minimum Stack (Min in O(1))

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Evaluate each approach

Final Answer:

Quick Check:

Solution

Step 1: Understand tail pointer semantics

Step 2: Calculate rear element index

Final Answer:

Quick Check:

Solution

Step 1: Understand multiPop operation

Step 2: Analyze one-queue approach

Step 3: Evaluate other options

Final Answer:

Quick Check:

Solution

Step 1: Understand the complexity introduced by '*'

Step 2: Evaluate approaches for handling wildcards

Step 3: Rule out brute force due to exponential possibilities

Final Answer:

Quick Check:

Solution

Step 1: Analyze effect of negative values on monotonic stack

Step 2: Confirm no structural changes needed

Final Answer:

Quick Check:

Ready to prove it?