Last Stone Weight

1. Problem & Core Objective

Repeatedly smash the two heaviest stones together:

• if they weigh the same, both are destroyed
• otherwise the lighter is destroyed and the heavier becomes heavier − lighter

Return the weight of the last remaining stone, or 0 if none remain.

stones = [2,7,4,1,8,1]

7,8 → 1        [2,4,1,1,1]
2,4 → 2        [2,1,1,1]
2,1 → 1        [1,1,1]
1,1 → 0        [1]
→ 1

Constraints: 1 <= stones.length <= 30 · 1 <= stones[i] <= 1000

What's actually being tested: recognising "repeatedly take the largest" as a max-heap, and noticing that the set changes between every extraction — which is what rules out sorting once. It's the simplest possible statement of "heap, not sort", which is why it's here.

2. First-Principles Thought Process

Read the loop literally

The process is: take the two heaviest, combine them, put the result back, repeat. Two operations dominate — extract the maximum and insert.

That pairing is exactly a heap's job description.

Why sorting once fails

Sort descending and you get the two heaviest immediately. But the smash produces a new stone whose weight is a difference, and that stone has to rejoin the collection in the right place.

So after every step you'd either re-sort — O(n log n) per round, O(n² log n) overall — or binary-search the insertion point and shift, O(n) per insert.

A heap re-inserts in O(log n) because it maintains only enough order to expose the maximum, not a full ordering.

Why a max-heap here, unlike question 1

Question 1 wanted a min-heap despite asking for "largest", because it was keeping a bounded set and needed the smallest kept element. Here there's no bounded set — the problem literally asks for the largest element each round, so the max-heap is direct.

Worth noticing the difference: "the k-th largest of a stream" inverts the heap; "repeatedly take the largest" does not. Reading which one you have is the skill.

Termination

Each round removes two stones and adds at most one, so the count strictly decreases. At most n − 1 rounds, ending with one stone or none.

3. Solution Paths

Approach 1 — Sort, extract, re-insert (brute force)

public int lastStoneWeight(int[] stones) {
    List<Integer> list = new ArrayList<>();
    for (int s : stones) list.add(s);

    while (list.size() > 1) {
        Collections.sort(list, Collections.reverseOrder());   // re-sort every round
        int a = list.remove(0), b = list.remove(0);
        if (a != b) list.add(a - b);
    }
    return list.isEmpty() ? 0 : list.get(0);
}

• Time O(n² log n) · Space O(n)

Counter-questions on this approach

⭐ "Why re-sort every round rather than sorting once?"

Because the smash creates a value that didn't exist before — a − b — and it has to take its correct position. Sorting once gives me the initial order, but the first smash invalidates it.

That's the signal for a heap: the collection changes between extractions, so I need a structure that supports insert and extract-max together, not a one-time ordering.

⭐ "What if you binary-searched the insertion point instead of re-sorting?"

Better — O(log n) to locate, but O(n) to shift elements in an ArrayList, so O(n²) overall instead of O(n² log n). At n = 30 both are trivially fast.

The heap gets it to O(n log n) and, more importantly, expresses the intent directly: I want the maximum and I want to insert, and I don't care about anything else's order.

"list.remove(0) — any issue?"

It's O(n) on an ArrayList because everything shifts left. Doing it twice per round compounds the cost. A LinkedList would make removal from the front O(1) but sorting and random access worse. Neither is the right structure; that's the point.

"At n = 30, isn't this fine?"

Completely — 30 stones means at most 29 rounds, so even the worst version runs instantly. The objection is not runtime, it's that the problem is a textbook heap and reaching for repeated sorting suggests you didn't recognise it.

Approach 2 — Max-heap (optimal)

public int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int s : stones) maxHeap.offer(s);

    while (maxHeap.size() > 1) {
        int a = maxHeap.poll();        // heaviest
        int b = maxHeap.poll();        // second heaviest
        if (a != b) maxHeap.offer(a - b);
    }
    return maxHeap.isEmpty() ? 0 : maxHeap.peek();
}

Trace — [2,7,4,1,8,1]:

Answer 1 ✓

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "Why a != b rather than pushing a - b unconditionally?"

When the stones are equal the difference is 0, and a stone of weight 0 doesn't exist — both are destroyed. Pushing 0 would leave a phantom stone in the heap.

It would also change the answer: the final peek() could return 0 when a real stone remains, or the loop could run an extra round smashing a zero against a real stone. The guard is load-bearing.

An equivalent formulation pushes unconditionally and filters zeros out, but the guard is cleaner and expresses the rule directly.

⭐ "Why Comparator.reverseOrder() rather than (a, b) -> b - a?"

Overflow safety and clarity. Subtraction-based comparators are wrong when the difference exceeds int range — with weights capped at 1000 it can't happen here, but it's a habit worth keeping, and reverseOrder() states the intent without arithmetic.

"Why is a guaranteed to be at least b?"

Because it was polled first from a max-heap, so a >= b. That's what makes a − b non-negative — no absolute value needed. If I'd polled from a min-heap and reversed the subtraction I'd have to be careful; the heap's ordering is doing that work.

"Why size() > 1 rather than !isEmpty()?"

Because a smash needs two stones. With one left there's nothing to combine, so the loop must stop. !isEmpty() would poll once and then poll null, throwing a NullPointerException on unboxing.

"What's the actual complexity?"

Building the heap is O(n) if constructed from a collection, or O(n log n) via n offers. Each round does two polls and at most one offer — O(log n) — and there are at most n − 1 rounds. So O(n log n) overall, dominated by the heap operations.

"Could you build it with new PriorityQueue<>(list) for the O(n) heapify?"

Only for the natural ordering. That constructor doesn't take a comparator, so for a max-heap you'd need new PriorityQueue<>(n, Comparator.reverseOrder()) and then addAll, which is O(n log n). Or negate every value and use a min-heap, which is ugly. At n = 30 it's irrelevant — worth knowing the API limitation though.

Comparison

4. Why the Optimal Wins

The set changes after every extraction, so a one-time sort is invalidated immediately. The choice is between re-establishing full order repeatedly — expensive and far more than needed — and maintaining just the property that exposes the maximum.

A heap maintains exactly that: parent ≥ children, which puts the maximum at the root and costs O(log n) to restore after a change. Everything else stays unordered, which is why it's cheap.

The framing worth keeping:

"Repeatedly take the largest, then put something back" is a max-heap. Sorting is for a collection that stops changing.

5. Java Prerequisites

Max-heap construction

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Collections.reverseOrder() is equivalent. Avoid (a, b) -> b - a — it overflows.

The extract-combine-reinsert loop

while (heap.size() > 1) {
    int a = heap.poll(), b = heap.poll();
    if (a != b) heap.offer(a - b);
}

poll returns null when empty, and unboxing that into an int throws NullPointerException — which is why the loop guard is size() > 1.

peek vs poll — peek reads without removing; poll removes and returns.

6. Interview Communication Guide

Clarifying questions: What if two stones are equal (both destroyed — confirm, it's the guard)? What if the array has one stone (return it; no smash happens)? Can weights be zero (no, >= 1)? Does the input need to be preserved (doesn't matter — I copy into the heap)?

The pitch

"The process is literally 'take the two heaviest, combine, put the result back, repeat'. That's extract-max plus insert, which is a heap's job description.

Sorting once doesn't work, because the smash produces a new value — the difference — that has to rejoin the collection in the right place. So the ordering is invalidated after every single round. I'd either re-sort each time, O(n² log n), or binary-search and shift, O(n²).

A max-heap maintains only enough order to expose the maximum, so re-inserting is O(log n). Poll twice, and if the two differ, offer the difference back.

The guard a != b matters: equal stones destroy each other, so pushing a zero would leave a phantom stone that could be returned as the answer.

And the loop condition is size() > 1, not !isEmpty(), because a smash needs two stones — polling from a one-element heap would return null and throw on unboxing.

O(n log n) overall.

Worth contrasting with the previous question: there I wanted a min-heap despite the word 'largest', because I was keeping a bounded set and needed its smallest member. Here the problem asks for the largest element directly, so the max-heap is the straightforward reading."

Edge cases to volunteer:

Name [2,2]. It's where the heap ends up empty and peek() would return null — the case that forces the isEmpty() check on the return, not just the loop guard.

7. Follow-Up Questions — Modified Constraints

⭐ "Smash the two LIGHTEST stones instead."

Swap to a min-heap — drop the comparator entirely, since PriorityQueue is a min-heap by default. Everything else is identical, which is a good check that the structure rather than the comparator was doing the thinking.

⭐ "Minimise the final stone weight by choosing which stones to smash."

LeetCode 1049, and a completely different problem — it's partition into two subsets with minimal difference, solvable by subset-sum DP at O(n · sum). The greedy "always take the two heaviest" is not optimal when you get to choose. Worth naming loudly, because the problems look adjacent and aren't.

"Return the whole sequence of smashes, not just the final weight."

Record each (a, b, result) triple as you go. O(n) extra space, no complexity change — the heap already visits them in the required order.

"What if there were 10^6 stones?"

The heap is still O(n log n) and handles it. Building via addAll is O(n log n); if you could use the natural ordering, the collection constructor heapifies in O(n). At that scale you'd also want int[]-backed heap rather than boxed Integer, to avoid a million object allocations.

"What if weights were floating point?"

a != b becomes unsafe — floating-point equality is fragile, so near-equal stones might not cancel. You'd compare with an epsilon, and decide deliberately whether a difference below that epsilon counts as destruction. This is where the integer constraint is quietly doing work.

"Could you avoid a heap entirely if the weights were small?"

Yes — with weights bounded by 1000, counting sort into a 1001-element bucket array gives extract-max in O(max) by scanning down, or O(1) amortised if you track the current maximum. That's O(n + max) overall and beats the heap when the value range is small. A nice reminder that bounded values often beat comparison-based structures.