Replay an Operation Log on a Min-Heap
Solve this ProblemYou are given a log of operations to run against an initially empty min-heap: insert a value, extractMin (remove and report the smallest value), peekMin (report the smallest value without removing it) and size (report how many values are stored). Return the answer produced by every extractMin, peekMin and size operation, in order. Asking an empty heap for its minimum reports -1.
The heap can be implemented as a simple unsorted list, but then every minimum query is a full scan. The array-backed binary heap keeps the minimum at index 0 and repairs itself along a single root-to-leaf path after each change, so both inserting and extracting cost O(log n).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ ops.length ≤ 100, and values.length equals ops.length - ◆
Each op is "insert", "extractMin", "peekMin" or "size"; the matching values entry is only read for "insert" - ◆
0 ≤ values[i] ≤ 1000 for every "insert" - ◆
"extractMin" and "peekMin" on an empty heap report -1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Unsorted List With a Full Scan for the Minimum
BruteStore every inserted value in a plain unsorted list, so an insert is a single append. Every time the minimum is needed — for peekMin or extractMin — scan the entire list to find the smallest entry; extractMin then overwrites that slot with the last element and shrinks the list by one. Inserts are cheap, but each minimum query has to look at every stored value, so a long log of queries against a large list becomes quadratic.
O(n²)O(n)1class Solution {
2 public List<Integer> replayMinHeap(String[] ops, int[] values) {
3 List<Integer> items = new ArrayList<>();
4 List<Integer> answers = new ArrayList<>();
5 for (int i = 0; i < ops.length; i++) {
6 String op = ops[i];
7 if (op.equals("insert")) {
8 items.add(values[i]);
9 } else if (op.equals("size")) {
10 answers.add(items.size());
11 } else if (items.isEmpty()) {
12 answers.add(-1);
13 } else {
14 int minIndex = 0;
15 for (int j = 1; j < items.size(); j++) {
16 if (items.get(j) < items.get(minIndex)) minIndex = j;
17 }
18 answers.add(items.get(minIndex));
19 if (op.equals("extractMin")) {
20 items.set(minIndex, items.get(items.size() - 1));
21 items.remove(items.size() - 1);
22 }
23 }
24 }
25 return answers;
26 }
27}Optimal — Array-Backed Binary Min-Heap
OptimalStore the heap in a flat array where the children of index i live at 2i+1 and 2i+2, and keep the rule that every parent is ≤ both of its children — which puts the minimum at index 0, so peekMin is free. Insert appends the value at the end and sifts it up, swapping with its parent while the parent is larger. extractMin returns index 0, moves the last element into the root and sifts it down, always swapping with the smaller child. Each repair walks a single root-to-leaf path of about log₂ n levels.
O(n log n)O(n)1class Solution {
2 public List<Integer> replayMinHeap(String[] ops, int[] values) {
3 int[] heap = new int[ops.length];
4 int size = 0;
5 List<Integer> answers = new ArrayList<>();
6 for (int i = 0; i < ops.length; i++) {
7 String op = ops[i];
8 if (op.equals("insert")) {
9 int child = size++;
10 heap[child] = values[i];
11 while (child > 0 && heap[(child - 1) / 2] > heap[child]) {
12 int parent = (child - 1) / 2;
13 int tmp = heap[parent]; heap[parent] = heap[child]; heap[child] = tmp;
14 child = parent;
15 }
16 } else if (op.equals("size")) {
17 answers.add(size);
18 } else if (size == 0) {
19 answers.add(-1);
20 } else if (op.equals("peekMin")) {
21 answers.add(heap[0]);
22 } else {
23 answers.add(heap[0]);
24 heap[0] = heap[--size];
25 int node = 0;
26 while (true) {
27 int left = 2 * node + 1, right = left + 1, smallest = node;
28 if (left < size && heap[left] < heap[smallest]) smallest = left;
29 if (right < size && heap[right] < heap[smallest]) smallest = right;
30 if (smallest == node) break;
31 int tmp = heap[node]; heap[node] = heap[smallest]; heap[smallest] = tmp;
32 node = smallest;
33 }
34 }
35 }
36 return answers;
37 }
38}