Katkat
Back

Design stack with O(1) minimum query

AnthropicSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to augment a standard stack with metadata to perform efficient minimum queries without sacrificing the constant-time complexity of stack operations.

Problem Description

Design a MinStack data structure that supports standard stack operations (push, pop, top) and a special getMin operation, all in constant time O(1).

Implement the MinStack class with the following methods:

  • push(val: int): Pushes the element val onto the stack.
  • pop(): Removes the element on the top of the stack.
  • top(): Gets the top element of the stack.
  • getMin(): Retrieves the minimum element currently in the stack.

Constraints

  • All operations must be O(1).
  • You may assume pop, top, and getMin are only called on non-empty stacks.
  • Values can be negative, zero, or positive integers.

Examples

stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
stack.getMin() # Returns -3
stack.pop()
stack.top()    # Returns 0
stack.getMin() # Returns -2

Edge Cases to Consider

  • Multiple identical minimum values (e.g., pushing -3 twice).
  • Rapidly alternating values (e.g., -5, 10, -5, 10).
  • Empty stacks (though the problem guarantees non-empty operations, consider how your implementation initializes).

Hints

Hint 1

Consider storing an extra piece of information alongside each value in the stack to track the minimum value at that specific depth.

Hint 2

Think about using a secondary stack (or a linked list of tuples) to keep track of the minimum value seen so far for every level of the main stack.

Hint 3

When pushing a new value, the new minimum is simply `min(current_value, previous_minimum)`. When popping, you can simply remove the corresponding record from your tracking mechanism.

Follow-up questions

  • What is the space complexity of your solution, and can you optimize it if there are many duplicate values?
  • How would you modify this design if we also needed to retrieve the maximum value in O(1) time?
  • If the stack could grow to millions of elements, are there any memory constraints or cache locality issues to consider with your chosen approach?