Last Stone Weight — LeetCode 1046 Max-Heap Simulation

Problem Statement#

You have a collection of stones with positive integer weights. Each turn, take the two heaviest stones and smash them. If equal, both are destroyed; otherwise the lighter one is destroyed and the heavier becomes their difference. Return the weight of the last stone (or 0 if all are gone).

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

Input:  stones = [2, 7, 4, 1, 8, 1]
Output: 1

Input:  stones = [1]
Output: 1

Why This Problem Matters#

LeetCode 1046 Last Stone Weight is a fan-favorite Amazon and Google phone-screen problem because it tests one thing cleanly: can you reach for a max-heap when the problem says "two heaviest"? It also tests Python's max-heap idiom (negate values) and JavaScript heap implementation skills.

Beyond the interview, this is a classic simulation pattern: repeatedly take the extremes, combine them, and reinsert. The same pattern appears in Huffman coding, Connect Sticks, and game theory.

Keywords: "max heap simulation", "two largest interview", "priority queue smash", "FAANG heap warmup".

The Core Insight#

Every turn we need the two largest. A sorted array would cost O(n) to extract; a max-heap costs O(log n). Pop two, push the difference (if any), repeat until 0 or 1 stone remains.

Python has only a min-heap, so negate values on push and pop. JavaScript has nothing — write a max-heap class or invert the comparator.

Visual Dry Run#

Final answer: 1 (from row 1 push).

Solution (Optimal)#

import heapq
 
class Solution:
    def lastStoneWeight(self, stones):
        h = [-s for s in stones]
        heapq.heapify(h)
        while len(h) > 1:
            a = -heapq.heappop(h)
            b = -heapq.heappop(h)
            if a != b:
                heapq.heappush(h, -(a - b))
        return -h[0] if h else 0

class MaxHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    size() { return this.h.length; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let s = i;
            if (l < n && this.h[l] > this.h[s]) s = l;
            if (r < n && this.h[r] > this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}
 
var lastStoneWeight = function(stones) {
    const h = new MaxHeap();
    for (const s of stones) h.push(s);
    while (h.size() > 1) {
        const a = h.pop();
        const b = h.pop();
        if (a !== b) h.push(a - b);
    }
    return h.size() ? h.pop() : 0;
};

Time: O(n log n) — each of up to n smashes does two pops and one push, each O(log n). Space: O(n) — heap stores all stones initially.

Common Mistakes#

• Using a min-heap and forgetting to negate — produces wrong order.
• Forgetting to push the difference back after a smash with unequal weights.
• Returning -1 or empty on the all-destroyed case instead of 0.
• Re-sorting an array each iteration — O(n^2 log n) and rejected on bigger inputs.
• Mutating the input array in unexpected ways instead of working on a heap copy.

Interview Tips#

• Open with: "Two heaviest each turn — that's a max-heap."
• For Python, mention the negation trick before writing code.
• For JavaScript, ask whether you can assume a heap library or should write one.
• Explicitly state the termination condition: heap size <= 1.

Follow-up Questions#

• What if stones have arbitrary precision (BigInt)? Heap still works; comparisons stay O(1) per step.
• What if you must record the order of smashes? Track tuples (-weight, index).
• What about Last Stone Weight II (LC 1049)? That is a 0/1 knapsack DP, not a heap.
• Can you do this in-place? Yes — heapify the input array, no extra allocation.

Key Takeaways#

• LeetCode 1046 reduces to repeated max-heap pop-pop-push.
• Python's heapq is min-only; negate values for max-heap behavior.
• Time is O(n log n), space O(n).
• The pattern generalizes to Huffman and Connect Sticks.
• Watch for the equal-weight branch: do not push 0 back.
• Heapify the input in O(n) — do not push one by one if you start with all stones.
• Last Stone Weight II is a different (DP) problem despite the similar name.