Min Stack
Updated
Problem statement
operations and values form a script of calls on an integer stack with a minimum query. Call i is operations[i]. When that call is "push", the number to push is values[i]; for every other call, values[i] has no meaning. The stack is empty before call 0.
Calls either change the stack or read it, never both:
- Changes:
"push"placesvalues[i]at the top, and"pop"discards the newest value still stored. - Reads:
"top"gives the most recently pushed value still in the stack, and"getMin"gives the minimum over all values currently stored.
Each read appends one number to the answer array, and changes append nothing. Return the answer array.
Aim for O(1) time per call. The official tests are small enough that a correct slower solution also finishes in time.
Function
runMinStack(operations: String[], values: int[]) → int[]Examples
Example 1
operations = ["push","getMin","push","push","top","getMin","pop","pop","top","getMin"]values = [12,0,20,9,0,0,0,0,0,0]return = [12,9,9,12,12]- With only
12stored,getMingives12. - After
20and then9go on,9is on top and is also lower than12and20, sotopandgetMingive9and9. - The two pops take off
9and20, in that order, and both reads go back to12, the value pushed first.
Example 2
operations = ["push","push","push","push","getMin","pop","getMin","pop","getMin","top"]values = [6,10,6,1,0,0,0,0,0,0]return = [1,6,6,10]- Bottom
6, then10, then6, then1on top:getMingives1. - Popping
1leaves two6s, one at the bottom and one third from the bottom, sogetMingives6. - Popping the upper
6still leaves the6at the bottom.getMinstays6, whiletopis now10.
Example 3
operations = ["push","push","pop","push","top","getMin"]values = [-100000,100000,0,-5,0,0]return = [-5,-100000]Six calls give only two numbers, because push and pop add nothing to the answer. After 100000 is popped, -5 goes on top of -100000, the lowest allowed value. top gives -5 and getMin gives -100000.
Constraints
1 <= operations.length <= 3000values.length == operations.length- Allowed call names:
"push","pop","top","getMin". -10^5 <= values[i] <= 10^5- Before any
"pop","top"or"getMin"call, the pushes so far outnumber the pops.
More Capital One interview questions
- Count Records Present in A but Not BPHONE SCREEN · Seen Oct 2026
- LRU CachePHONE SCREEN · ONSITE INTERVIEW · Seen May 2026
- Maximum Subarray SumPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2025
- Ten-Pin Bowling Frame ScoresPHONE SCREEN · Seen Nov 2023
- Invert a Binary TreePHONE SCREEN · Seen Dec 2020
- Count How Often a Word Appears in a ParagraphPHONE SCREEN
- In-Memory File System With Directory SizesPHONE SCREEN · ONSITE INTERVIEW
- Pick the K Nearest Grid Points to (0, 0)PHONE SCREEN · ONSITE INTERVIEW
- The Nth Number in the Fibonacci SequencePHONE SCREEN · ONSITE INTERVIEW
- Digit-Coded Card ValidationONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Stack with Middle OperationsMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Max StackLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Max StackZipline · ONSITE INTERVIEW
- Max StackBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- LRU CacheLotusFlare · ONSITE INTERVIEW
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheGimlet Labs · PHONE SCREEN
- Billing Log with Undo and RedoReddit · PHONE SCREENReddit interview questions
- KV Store with Nested TransactionsApplied Intuition · PHONE SCREEN · ONSITE INTERVIEWApplied Intuition interview questions
- LRU CacheBNSF Railway · PHONE SCREENBNSF Railway interview questions
Capital One interview experiences
- Capital One Experienced Engineer Power Day and OA: 6 Experiences
- Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
- Capital One TDP Agentic Round (AI Coding): 7 Experiences
- Capital One SWE Power Day, Level Not Reported: 6 Experiences
- Capital One TIP Intern OA and Power Day: 13 Experiences
- Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)