Problem · Array

Execute a Min-Heap Operation Sequence

Learn this problem
Mediumpony.ai logopony.aiFULLTIMEPHONE SCREEN

Problem statement

Implement a min-heap from scratch and execute an ordered batch of operations.

The arrays operations and values have equal length. Each operation is one of:

  • insert: insert values[i] into the heap and append null to the result.
  • removeMin: remove and append the minimum value as a decimal string. If the heap is empty, append null. The corresponding values[i] is ignored.

Duplicate values are stored independently. Return one result string for every operation in the same order.

Do not use a built-in heap or priority-queue data structure.

Function

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

Examples

Example 1

operations = ["insert", "insert", "removeMin", "removeMin", "removeMin"]values = [5, 2, 0, 0, 0]return = ["null", "null", "2", "5", "null"]

The two inserted values are removed in increasing order. The last removal sees an empty heap.

Example 2

operations = ["insert", "insert", "insert", "removeMin", "removeMin"]values = [-3, -3, 4, 0, 0]return = ["null", "null", "null", "-3", "-3"]

Both copies of -3 are retained and removed independently.

Example 3

operations = ["removeMin", "insert", "removeMin"]values = [0, 7, 0]return = ["null", "null", "7"]

An empty removal does not prevent a later insertion and successful removal.

Constraints

  • 1 <= operations.length == values.length <= 100000
  • operations[i] is either insert or removeMin.
  • -2147483648 <= values[i] <= 2147483647
  • The heap contains at most 100000 values at any time.
drafts saved locally
public String[] runMinHeap(String[] operations, int[] values) {
    // Write your code here.
}
operations["insert", "insert", "removeMin", "removeMin", "removeMin"]
values[5, 2, 0, 0, 0]
expected["null", "null", "2", "5", "null"]
checking account