Replay an Operation Log on a Max-Heap With a Replace-Top Command

Easy20–25 min

Topics

HeapMax HeapDesign

Companies

AmazonGoogleAdobe

Run a log of operations against an initially empty max-heap: insert a value, extractMax (remove and report the largest value), peekMax (report it without removing) and replaceMax — which removes the current largest value, adds a new value in its place, and reports the value it removed. Return the answer reported by every extractMax, peekMax and replaceMax, in order; any of them on an empty heap reports -1 (and replaceMax still adds its value).

Re-sorting the whole list before every query gives the right answers, but does far more work than the question needs. A binary max-heap keeps only the maximum in a known place and repairs itself along one path after each change — and replaceMax shows a neat shortcut: overwrite the root and sift down once, instead of extracting and inserting.

Test Case 1:

Input:ops = ["insert","insert","insert","replaceMax","extractMax","peekMax"], values = [4,9,6,5,0,0]

Output:[9, 6, 5]

Explanation:replaceMax removes 9 and adds 5 (heap holds 4, 6, 5); extractMax then removes 6; peekMax shows 5.

Test Case 2:

Input:ops = ["insert","replaceMax","peekMax"], values = [3,20,0]

Output:[3, 20]

Explanation:The replacement can itself become the new maximum: 3 is removed, 20 goes in, and peekMax sees 20.

Test Case 3:

Input:ops = ["replaceMax","peekMax","extractMax","extractMax"], values = [7,0,0,0]

Output:[-1, 7, 7, -1]

Explanation:replaceMax on an empty heap only inserts (reporting -1); the later extractMax calls drain it, and the final one finds it empty.

Constraints

◆1 ≤ ops.length ≤ 100, and values.length equals ops.length
◆Each op is "insert", "extractMax", "peekMax" or "replaceMax"; the matching values entry is only read for "insert" and "replaceMax"
◆0 ≤ values[i] ≤ 1000
◆"replaceMax v" removes the current maximum, adds v, and reports the removed maximum; on an empty heap it just adds v and reports -1
◆"extractMax" and "peekMax" 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 — Re-Sort the Whole List Before Every Query

Brute

Keep every value in a plain list and, each time the maximum is needed (peekMax, extractMax or replaceMax), sort the entire list from largest to smallest so the maximum sits at the front. extractMax then drops the front element and replaceMax overwrites it with the new value. The answers are right, but every query pays for a full O(n log n) sort even though only a single element — the maximum — was ever needed.

TimeO(n² log n)

SpaceO(n)

Java

Try it out

class Solution {
    public List<Integer> replayMaxHeap(String[] ops, int[] values) {
        List<Integer> items = new ArrayList<>();
        List<Integer> answers = new ArrayList<>();
        for (int i = 0; i < ops.length; i++) {
            String op = ops[i];
            if (op.equals("insert")) {
                items.add(values[i]);
            } else if (items.isEmpty()) {
                answers.add(-1);
                if (op.equals("replaceMax")) items.add(values[i]);
            } else {
                items.sort(Collections.reverseOrder());
                answers.add(items.get(0));
                if (op.equals("extractMax")) {
                    items.remove(0);
                } else if (op.equals("replaceMax")) {
                    items.set(0, values[i]);
                }
            }
        }
        return answers;
    }
}

Optimal — Array-Backed Binary Max-Heap With sift-up and sift-down

Optimal

Keep the values in a binary max-heap: an array where the children of index i are 2i+1 and 2i+2 and every parent is ≥ its children, so the maximum is always at index 0 and peekMax is free. insert appends and sifts up. extractMax moves the last element to the root and sifts down. replaceMax is a special case that does the same work in one pass: instead of extracting and then inserting (two repairs), it simply overwrites the root with the new value and sifts it down once — if the new value is still the largest it doesn't move at all.

TimeO(n log n)