Last Stone Weight

easyTests passed 2026-11-11v1.0.0
TC: O(N log N)|SC: O(N)
HeapsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Simulate greedy extraction of the two heaviest stones using a max-heap (`-val` in Python min-heap): while `len(h) > 1`, pop `y`, pop `x`, and if `y != x` push `y - x`.

2. Complexity Bounds & Proof

Each round consumes at least one stone; at most N iterations execute O(log N) heap pops/pushes.

3. Minimal Idiomatic Code

def lastStoneWeight(stones: list[int]) -> int:
    h = [-s for s in stones]
    heapq.heapify(h)
    while len(h) > 1:
        y = -heapq.heappop(h)
        x = -heapq.heappop(h)
        if y != x:
            heapq.heappush(h, -(y - x))
    return -h[0] if h else 0

4. Failure Modes & Interview Follow-ups

Pitfalls:- Returning without `h[0]` sign inversion when using negated values in Python. - Forgetting empty heap edge case (all stones annihilated -> return 0).
Follow-ups:- Last Stone Weight II asks for minimum leftover overall, which reduces to 0/1 Knapsack partition (`sum - 2 * subsetSum`).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Kth Largest Element in a Stream (O(N log k))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.