Quick Overview

Design a stack that supports push, pop, top and reading its current minimum in constant time, then run it over a sequence of operations and return what the reads produce. Tests data structure design, duplicate minimum values and keeping auxiliary state consistent on every pop.

Stack with Constant-Time Minimum over a Sequence of Operations

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a stack that supports pushing an element, popping the top element, reading the top element, and reading the smallest element currently in the stack, with every one of these operations taking constant time. To make the design testable as a single function, process a sequence of operations on an initially empty stack and return the values that the reading operations produce. ### Function Signature ```python def run_min_stack(ops: list[str], args: list[int]) -> list[int]: ``` ### Rules - `ops[i]` is one of `"push"`, `"pop"`, `"top"`, `"get_min"`. - `"push"` pushes `args[i]`. For every other operation, `args[i]` is `0` and is ignored. - `"pop"` removes the top element and produces no output. - `"top"` outputs the top element; `"get_min"` outputs the smallest element currently in the stack. Neither removes anything. - The stack can hold equal values; each push is a separate element. - Return the outputs of `"top"` and `"get_min"` in the order the operations occur. If there are none, return an empty list. - Each operation must run in O(1) time; the tests include long sequences on which scanning the stack for every `"get_min"` is too slow. ### Constraints - `1 <= len(ops) = len(args) <= 10^5` - for `"push"`, `-2^31 <= args[i] <= 2^31 - 1`, the full signed 32-bit range - `"pop"`, `"top"` and `"get_min"` are only issued when the stack is non-empty ### Examples **Example 1** ```text Input: ops = ["push", "push", "push", "get_min", "pop", "top", "get_min"] args = [-2, 0, -3, 0, 0, 0, 0] Output: [-3, 0, -2] ``` After the three pushes the stack is `[-2, 0, -3]` (top last) and its minimum is `-3`. Popping removes `-3`; the top is then `0` and the minimum is `-2`. **Example 2** ```text Input: ops = ["push", "push", "push", "get_min", "pop", "get_min", "pop", "get_min"] args = [2, 1, 1, 0, 0, 0, 0, 0] Output: [1, 1, 2] ``` Two copies of the minimum `1` are pushed. After one is popped the minimum is still `1`; after the second is popped it becomes `2`.

Overview: Design a stack that supports push, pop, top and reading its current minimum in constant time, then run it over a sequence of operations and return what the reads produce. Tests data structure design, duplicate minimum values and keeping auxiliary state consistent on every pop.

Design a stack that supports pushing an element, popping the top element, reading the top element, and reading the smallest element currently in the stack, with every one of these operations taking constant time. To make the design testable as a single function, implement `run_min_stack(ops, args)`: apply the operations in `ops` (with their arguments in `args`), in order, to an initially empty stack, and return the values that the reading operations produce. ### Rules - `ops[i]` is one of `"push"`, `"pop"`, `"top"`, `"get_min"`. - `"push"` pushes `args[i]`. For every other operation, `args[i]` is `0` and is ignored. - `"pop"` removes the top element and produces no output. - `"top"` outputs the top element; `"get_min"` outputs the smallest element currently in the stack. Neither removes anything. - The stack can hold equal values; each push is a separate element. - Return the outputs of `"top"` and `"get_min"` in the order the operations occur. If there are none, return an empty list. - Each operation must run in O(1) time; scanning the stack for every `"get_min"` is too slow on long operation sequences. ### Constraints - `1 <= len(ops) = len(args) <= 10^5` - For `"push"`, `-2^31 <= args[i] <= 2^31 - 1`, the full signed 32-bit range; for every other operation `args[i]` is `0`. - `"pop"`, `"top"` and `"get_min"` are only issued when the stack is non-empty. - Every returned value is one of the pushed values, so no value exceeds 2^31 - 1 and every value fits in a signed 32-bit integer. ### Example 1 ```text Input: ops = ["push", "push", "push", "get_min", "pop", "top", "get_min"] args = [-2, 0, -3, 0, 0, 0, 0] Output: [-3, 0, -2] ``` After the three pushes the stack is `[-2, 0, -3]` (top last) and its minimum is `-3`. Popping removes `-3`; the top is then `0` and the minimum is `-2`. ### Example 2 ```text Input: ops = ["push", "push", "push", "get_min", "pop", "get_min", "pop", "get_min"] args = [2, 1, 1, 0, 0, 0, 0, 0] Output: [1, 1, 2] ``` Two copies of the minimum `1` are pushed. After one is popped the minimum is still `1`; after the second is popped it becomes `2`.

Constraints

  • 1 <= len(ops) = len(args) <= 10^5
  • ops[i] is one of "push", "pop", "top", "get_min"
  • For "push", -2^31 <= args[i] <= 2^31 - 1, the full signed 32-bit range; for every other operation args[i] is 0 and is ignored
  • "pop", "top" and "get_min" are only issued when the stack is non-empty
  • Every returned value is a pushed value, so no value exceeds 2^31 - 1 and every value fits in a signed 32-bit integer

Examples

Input: (['push'], [5])

Expected Output: []

Explanation: Minimum valid: a single push and no reading operation, so the result is empty.

Input: (['push', 'top'], [7, 0])

Expected Output: [7]

Explanation: Minimum valid: a single push followed by one top.

Hints

  1. After the smallest element is popped, the next "get_min" must be answered immediately, without looking through the rest of the stack.
  2. Equal values are separate elements: popping one copy of the minimum must not forget the copies still on the stack.
  3. Only "top" and "get_min" add to the result, in operation order; a sequence without them returns an empty list.

Loading coding console...

Show the approach

Approach

Keep two parallel stacks: values holds the elements, and mins[k] holds the minimum of the bottom k + 1 elements, i.e. the stack minimum at the moment element k was pushed. On push of v, append v to values, and append v to mins if mins is empty or v is smaller than its last entry, otherwise repeat the last entry. On pop, remove the last entry of both stacks. top reads values[-1] and get_min reads mins[-1]; only these two operations append to the output list.

Invariant: after every operation, mins[k] = min(values[0..k]) for every k. A push preserves it because the new entry is the minimum of v and the previous prefix minimum; a pop preserves it because removing the top element never changes any prefix below it. Therefore mins[-1] is always the minimum of the whole stack, and every operation does a constant amount of work.

Edge cases: equal values each get their own mins entry, so popping one copy of the minimum leaves the remaining copies in force; popping a non-minimum element leaves the minimum unchanged; when the stack is drained to empty, the next push starts a fresh minimum; the bounds -2^31 and 2^31 - 1 are only compared and copied, never added or subtracted, so nothing overflows (an encoding such as storing 2v - min would overflow 32-bit integers); a sequence with no top or get_min returns an empty list.

Time complexity:
O(n)
Space complexity:
O(n)