Last Stone Weight

Problem

You have a row of stones with integer weights. On each turn, take the two heaviest stones x ≤ y. If x == y both are destroyed; otherwise the lighter is destroyed and the heavier becomes y − x. Return the weight of the last remaining stone (0 if none remain).

Constraints

• 1 ≤ stones.length ≤ 30
• 1 ≤ stones[i] ≤ 1000

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

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

Java

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Max-heap so the two heaviest stones are always at the top.
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones) {
            heap.offer(stone);
        }
        while (heap.size() > 1) {
            int heaviest = heap.poll();
            int second = heap.poll();
            if (heaviest != second) {
                heap.offer(heaviest - second);
            }
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.