Interview Q&A / Data Structures & Algorithms

1. How do you design a stack that returns the minimum element in O(1)?

   Keep a second stack of minimums. On each push, also push the smaller of the new value and the current minimum. Pop from both together, and the top of the second stack is always the minimum.

   IntermediateQuick answerCoding1 min read
2. How do you find the next greater element for every item in an array?

   Use a monotonic stack of indices. Walk left to right; while the current value is greater than the value at the stack top, that top has found its next greater element. Then push the current index.

   IntermediateQuick answerCoding1 min read
3. How do you implement a queue using two stacks?

   Push new items onto an input stack. When you need to dequeue and the output stack is empty, pour everything from the input stack into the output stack, which reverses the order, then pop from the output stack.

   IntermediateQuick answerCoding1 min read