{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Min Stack – Solution & Complexity

Interview solutions
/
Min Stack

Solution Walkthrough

  1. Step 1: Start with the obvious simulation

    • A plain array-backed stack makes push, pop, and top easy.
    • But scanning the whole stack on every getMin would cost O(n) per query.

  2. Step 2: Mirror the minimum state

    • Maintain a second stack mins with the same depth as the main stack.
    • At each depth, store the minimum value seen so far, so the current minimum is always mins[-1].

  3. Step 3: Handle duplicates carefully

    • Push the new minimum for every element, even if it matches the previous minimum.
    • Then one pop removes both the top value and the corresponding minimum snapshot.

  4. Step 4: Final solution (all languages)

    Two synchronized stacks keep every operation at constant time.

    def min_stack(operations: list[str], values: list[int]) -> list[int]:
    stack: list[int] = []
    mins: list[int] = []
    answer: list[int] = []

    for operation, value in zip(operations, values):
        if operation == "push":
            stack.append(value)
            mins.append(value if not mins else min(value, mins[-1]))
        elif operation == "pop":
            stack.pop()
            mins.pop()
        elif operation == "top":
            answer.append(stack[-1])
        else:
            answer.append(mins[-1])

    return answer

  5. Step 5: Complexity summary

    • Time: O(q) total for q operations, so O(1) amortized and worst-case per operation.
    • Space: O(q) in the worst case when every operation is a push.

FAQ

See also

Practice Min Stack online (run code in the browser)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)Daily Temperatures solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?