Last Stone Weight

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

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


def lastStoneWeight(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, giving O(n² log n). With n <= 30 this passes, but it does Θ(n log n) work per round to answer a single question — what are the two largest? — that a heap answers in O(log n).

Approach 2 — Max-heap

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 and push. Python’s heapq is min-only, so store -weight; the numerically smallest entry is then the heaviest stone.

A max-heap holding {8, 7, 4, 2, 1, 1} keeps the largest weight at the root, so reading the maximum is O(1):

graph TD
    A[8] --> B[7]
    A --> C[4]
    B --> D[2]
    B --> E[1]
    C --> F[1]

import heapq
from typing import List


def lastStoneWeight(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):

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)

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


def lastStoneWeight(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, 2, 4, 7, 8]; pop 8 and 7, insort 1 → [1, 1, 1, 2, 4]; pop 4 and 2, insort 2 → [1, 1, 1, 2]; pop 2 and 1, insort 1 → [1, 1, 1]; pop 1 and 1 (equal) → [1]. One stone left, answer 1.

Each insort is O(log n) to find the spot but O(n) to shift elements, so O(n²) worst case. Fine at n = 30 and a 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.