Stack With Constant-Time Minimum
Updated
Problem statement
Build a stack of integers that can also tell its smallest value at any moment. It supports:
push: putvalues[i]on top.pop: remove the top value (outputs nothing).top: output the top value without removing it.getMin: output the smallest value currently in the stack.
Run operations in order, starting from an empty stack, and return the outputs of top and getMin in order. Try to make every operation take O(1) time. The judge only checks the outputs.
Function
runMinStack(operations: String[], values: int[]) → int[]Examples
Example 1
operations = ["push","push","push","getMin","pop","top","push","getMin","pop","pop","getMin"]values = [5,2,7,0,0,0,1,0,0,0,0]return = [2,2,1,5]After pushing 5, 2 and 7 the smallest value is 2. pop removes 7, so top is 2. Pushing 1 makes the minimum 1. Two pops remove 1 and 2, leaving only 5, so the last getMin is 5. Outputs: 2, 2, 1, 5.
Example 2
operations = ["push","push","getMin","pop","getMin","top"]values = [3,3,0,0,0,0]return = [3,3,3]The value 3 is pushed twice. Popping one copy still leaves a 3, so the minimum stays 3. Outputs: 3, 3, 3.
Example 3
operations = ["push","push","push","getMin","pop","getMin","top"]values = [-4,6,-9,0,0,0,0]return = [-9,-4,6]The stack holds -4, 6, -9 (top last), so the minimum is -9. After pop removes -9, the minimum goes back to -4 while the top is 6. Outputs: -9, -4, 6.
Constraints
1 <= operations.length <= 2000andvalues.length == operations.length- each
operations[i]is one ofpush,pop,top,getMin -10^9 <= values[i] <= 10^9whenoperations[i]ispush, andvalues[i] == 0otherwisepop,topandgetMinare only called when the stack is not empty
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Implement a Queue Using Two StacksOracle · PHONE SCREENOracle interview questions
- Billing Log with Undo and RedoReddit · PHONE SCREENReddit interview questions
- KV Store with Nested TransactionsApplied Intuition · PHONE SCREEN · ONSITE INTERVIEWApplied Intuition interview questions
- Multiline Text Editor with Cursor MovementDatologyAI · PHONE SCREEN
- Layer History with Batch Undo and RedoFigma · OA · PHONE SCREENFigma interview questions
- Stack with Constant-Time Middle QueriesAmazon · PHONE SCREEN
- In-Memory Database with Transactions and SavepointsNextdoor · PHONE SCREENNextdoor interview questions
- Nested Recipe Cart TransactionsDecagon · PHONE SCREENDecagon interview questions
- Min StackMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- Text Editor, Part 2: Undo and RedoOpenAI · PHONE SCREENOpenAI interview questions