Last Stone Weight — InterviewPrepKit

Solving tips

Recognize a priority-queue simulation: each round needs the two largest values, so use a max-heap.
Python's heapq is min-only — negate weights on push and pop so the smallest stored value is the heaviest stone.
Pop y (heaviest) then x; only push back y - x when y > x, or you seed phantom weight-0 stones.
Target O(n log n) time and O(n) space; return 0 (not a crash) when the heap empties on total annihilation.

Problem

You have a pile of stones, each with a positive integer weight, given as an array stones.

Repeat the following until at most one stone remains: take the two heaviest stones, weights x <= y, and smash them together.

If x == y, both stones are destroyed.
If x < y, the stone of weight x is destroyed and the other stone’s weight becomes y - x.

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

Examples

stones = [2, 7, 4, 1, 8, 1] → 1. Smash 8 and 7 → 1 remains, pile [2, 4, 1, 1, 1]; smash 4 and 2 → 2, pile [2, 1, 1, 1]; smash 2 and 1 → 1, pile [1, 1, 1]; smash 1 and 1 → both gone, pile [1]. Answer 1.
stones = [1] → 1. A single stone is never smashed.
stones = [3, 3] → 0. Equal stones annihilate each other, leaving nothing.

Constraints

1 <= len(stones) <= 30
1 <= stones[i] <= 1000

Think about it first

Hint 1

Simulate the process literally — the only operation you ever need is "give me the two largest values currently in the pile."

Hint 2

Repeatedly scanning or re-sorting the list to find the two largest works but is quadratic. Which data structure hands you the maximum in O(log n) per extraction?

Hint 3

Python's `heapq` is a min-heap only — store each weight negated so the smallest stored value is the heaviest stone. Pop twice, push back the (negated) difference if nonzero, loop until one or zero items remain.

TL;DR

Max-heap simulation (negate values for Python’s min-heap): O(n log n) time, O(n) space.

Approach 1 — Brute force (re-sort every round)

Simulate directly: sort the pile each round, pull off the two largest, push back the difference.

from typing import List


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = list(stones)
        while len(stones) > 1:
            stones.sort()
            y = stones.pop()
            x = stones.pop()
            if y != x:
                stones.append(y - x)
        return stones[0] if stones else 0

Each round costs an O(n log n) sort and there are up to n − 1 rounds → O(n² log n). With n <= 30 this actually passes — the constraints don’t kill it — but it does Θ(n log n) work per round to answer a question (“what are the two biggest?”) that a heap answers in O(log n), which is the lesson the problem exists to teach.

Approach 2 — Max-heap

The insight: the simulation only ever needs the current maximum, twice per round. A binary heap (a complete tree where each parent outranks its children, stored flat in an array) gives O(1) peek and O(log n) pop/push. Python’s heapq is min-only, so store -weight and the numerically smallest entry is the heaviest stone.

import heapq
from typing import List


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

Walkthrough of stones = [2, 7, 4, 1, 8, 1] (heap shown as the multiset of positive weights it holds):

round	pop y	pop x	push back	pile after
1	8	7	1	{4, 2, 1, 1, 1}
2	4	2	2	{2, 1, 1, 1}
3	2	1	1	{1, 1, 1}
4	1	1	— (equal)	{1}

One stone left → return 1, matching the example.

Complexity: heapify is O(n); each of ≤ n − 1 rounds does at most three O(log n) heap operations → O(n log n) time, O(n) space (O(1) extra if you’re allowed to trash the input by heapifying it in place — negation forces a copy here).

Approach 3 — Sorted-list insertion (the honorable mention)

The insight: instead of a heap you can keep the pile sorted at all times and re-insert the difference in its correct position with binary search (bisect.insort). Same “always know the max” idea, different structure.

import bisect
from typing import List


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        pile = sorted(stones)
        while len(pile) > 1:
            y = pile.pop()
            x = pile.pop()
            if y > x:
                bisect.insort(pile, y - x)
        return pile[0] if pile else 0

Tracing the same example: pile starts [1, 1, 1, 2, 4, 7, 8]; pop 8, 7 → insort 1 → [1, 1, 1, 1, 2, 4]; pop 4, 2 → insort 2 → [1, 1, 1, 1, 2]; pop 2, 1 → insort 1 → [1, 1, 1, 1]; pop 1, 1 → [1, 1]; pop 1, 1 → []… careful — that trace shows why you must pop the two largest (list end), which this does; the final state after round 4 is [1], answer 1.

Each insort is O(log n) to find the spot but O(n) to shift elements → O(n²) worst case. Fine at n = 30, and a genuinely common interview answer, but the heap is the asymptotically right tool.

Common pitfalls

Forgetting Python’s heapq is a min-heap — pushing raw weights makes you smash the two lightest stones. Negate on push and on pop.
Pushing y - x even when x == y, seeding the pile with phantom weight-0 stones.
Returning heap[0] without re-negating, or crashing on an empty heap when all stones annihilate — the [3, 3] → 0 case.
Ordering the pops wrong: the first pop is y (heavier), the second is x; with y - x reversed you’d push negatives-of-negatives and corrupt the pile.

Pattern takeaway

When a process repeatedly consumes the current extreme element (max or min) and may push back a new value, that’s a priority-queue simulation: heapify once, then each round is a couple of O(log n) pops and pushes. In Python, “max-heap” is spelled “min-heap of negated values” — negate at the boundary (push and pop) and keep the rest of the logic in positive terms.