How should I practice Min Stack?

Start by reading the full statement, solve the visible examples, then compare the pattern against related DP World onsite interview problems in FastPrep.

Is Min Stack associated with DP World?

FastPrep tags this as a DP World onsite interview coding practice problem when the problem catalog has that company and stage context.

Min Stack

DP World● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Design a stack that can also report its smallest value. It supports four operations:

push: put values[i] on top of the stack.
pop: remove the value on top.
top: report the value on top without removing it.
getMin: report the smallest value in the stack without removing it.

The operations are given in order in operations, with a matching array values. Start with an empty stack and run every operation in order. Return the values reported by top and getMin, in the order they happen. push and pop report nothing.

A value that is pushed more than once is stored as separate entries. Each operation should take O(1) time.

Function

minStack(operations: String[], values: int[]) → int[]

Examples

Example 1

operations = ["push","push","push","getMin","pop","top","getMin"]values = [-2,0,-3,0,0,0,0]return = [-3,0,-2]

After pushing -2, 0 and -3, the smallest value is -3. The pop removes -3, so the top is now 0 and the smallest value is -2. The reported values are [-3,0,-2].

Example 2

operations = ["push","push","push","pop","getMin","pop","getMin"]values = [5,3,3,0,0,0,0]return = [3,5]

The value 3 is pushed twice. After one pop, one copy of 3 is still in the stack, so getMin reports 3. After the second pop, only 5 is left, so getMin reports 5.

Example 3

operations = ["push","top","getMin"]values = [7,0,0]return = [7,7]

With one value in the stack, it is both the top and the smallest value, so both queries report 7.

Constraints

1 <= operations.length <= 3 * 10^4
values.length == operations.length
Each operations[i] is "push", "pop", "top", or "getMin".
-2^31 <= values[i] <= 2^31 - 1
values[i] == 0 whenever operations[i] is not "push".
pop, top, and getMin are only called when the stack is not empty.