Last Stone Weight

easyHeap / Priority Queue31 stepsJava · Python · C++

Repeatedly smash the two heaviest stones: equal stones both vanish, otherwise the difference goes back. A max-heap always gives the two heaviest in O(log n).

▶ Watch the animated trace

Traced input: stones = [2, 7, 4, 1, 8, 1] → 1. Original problem: neetcode.io/problems/last-stone-weight

Complexity

BestO(n log n)

AverageO(n log n)

WorstO(n log n)

SpaceO(n)

Each smash removes at least one stone.

Key idea

Each round needs the two largest values: exactly what a max-heap provides.
Push back y - x only when it's non-zero.
Return the last stone, or 0 if none are left.

Common mistakes

Java's PriorityQueue is a min-heap; pass Collections.reverseOrder().
Re-sorting the array each round is O(n² log n).

Solution

Java

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

Python

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

C++

int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> heap(stones.begin(), stones.end());
    while (heap.size() > 1) {
        int y = heap.top(); heap.pop();
        int x = heap.top(); heap.pop();
        if (y != x) heap.push(y - x);
    }
    return heap.empty() ? 0 : heap.top();
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single stone Nothing to smash.	`stones = [1]`	`1`
Everything cancels Equal stones both vanish.	`stones = [2, 2]`	`0`
All the same Two cancel, one is left.	`stones = [3, 3, 3]`	`3`