Room 04 · The Grind — Heap / Priority Queue

Last Stone Weight

EASY✓ CHIP-TIMEDLC #1046 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Two heaviest stones keep colliding — equal weights destroy each other, unequal ones leave the difference behind — until at most one stone survives; report what's left, or zero if nothing does.

A pile of stones, each with its own weight, keeps colliding two at a time — always the two heaviest stones in the pile at that moment.

Equal weights annihilate each other completely; unequal weights leave behind a single new stone weighing the difference, which goes back into the pile for future rounds.

The smashing repeats until at most one stone remains, and the task is reporting that stone's weight, or zero if the pile empties out entirely.

stone counts run up to a few thousand
weights are positive integers within an ordinary range
always the two currently heaviest stones collide, never any other pair
the result is a single weight, zero when nothing survives

EX 01

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

→ 1

the classic mixed pile

EX 02

stones = [1]

→ 1

minimum size, single stone

EX 03

stones = [3, 3]

→ 0

one equal pair, both destroyed

The hintstake only what you need

HINT 1 THE NUDGE

Smashing the two heaviest stones together is the whole rule — the challenge is finding 'the two heaviest' fast, over and over, as the pile keeps changing shape.

HINT 2 THE STRUCTURE

Sorting the whole pile after every single collision to find the top two is way more work than the question needs — only the top of the pile ever changes on each round, not the middle or the bottom.

HINT 3 ONE STEP FROM THE ANSWER

Push every weight into a max-heap. Pop twice, smash them, and if a stone survives push the difference back in. Repeat until at most one weight remains.

Coach's boardthe pattern, step by step

THE LAST COLLISIONPATTERN · MAX-HEAP OF STONESstones = [2, 7, 4, 1, 8, 1]

STEP 1

Six stones. Load them into a max-heap — the two heaviest always float to the top.

STEP 1 / 9 · ← → WORK TOO

The splitstwo paces, two languages

grind/last-stone-weight.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 10 LN

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        pile = list(stones)
        while len(pile) > 1:
            pile.sort()  # full re-sort every round just to find the top two
            a = pile.pop()
            b = pile.pop()
            if a != b:
                pile.append(a - b)
        return pile[0] if pile else 0

TIME O(N² LOG N)SPACE O(N)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) {
            heap.offer(s);
        }
        while (heap.size() > 1) {
            int a = heap.poll();
            int b = heap.poll();
            if (a != b) {
                heap.offer(a - b);
            }
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 16 LN

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> pile = new ArrayList<>();
        for (int s : stones) {
            pile.add(s);
        }
        while (pile.size() > 1) {
            Collections.sort(pile);
            int a = pile.remove(pile.size() - 1);
            int b = pile.remove(pile.size() - 1);
            if (a != b) {
                pile.add(a - b);
            }
        }
        return pile.isEmpty() ? 0 : pile.get(0);
    }
}

TIME O(N² LOG N)SPACE O(N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED