Problem statement

You have stones with weights stones[i]. Each turn, smash the two heaviest stones together: equal weights destroy both; otherwise the heavier survives with weight y - x.

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

Example 1

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 8&7→1, 4&2→2, 2&1→1, 1&1→0, leaving 1.

Example 2

Input: stones = [1]
Output: 1

Constraints

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

Hints for Last Stone Weight

1. Hint 1

   A max-heap gives you the two heaviest stones in O(log n).

2. Hint 2

   Push back the difference when it's non-zero.

How to solve Last Stone Weight

The rules always ask for the two heaviest stones, and the smash puts a new stone back into the pile. That is exactly what a max-heap is for: it hands you the largest in O(log n) and absorbs the new stone just as cheaply. Simulate the process literally.

Approach

1. Put every stone into a max-heap.
2. While at least two stones remain, pop the two largest, y then x (so y >= x).
3. If they are equal, both are destroyed — push nothing back.
4. Otherwise push y - x, the surviving fragment.
5. When fewer than two stones remain, return the last one, or 0 if the pile is empty.

Why it works

The process is fully determined — at every turn the pair to smash is forced — so a direct simulation cannot go wrong; the only question is how fast you can find the two heaviest. Each turn removes two stones and adds at most one, so the pile shrinks by at least one per turn and the loop always terminates in at most n rounds.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• The pile can end up empty, not just with one stone — the answer is 0 in that case, and indexing blindly will crash.
• Push the difference back only when it is non-zero; pushing a 0 stone corrupts later rounds.
• Order matters when subtracting: it is y - x with y the larger, never the other way round.

Reference solution

Python

from typing import List
import heapq

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

Java

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

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();
}

JavaScript

var lastStoneWeight = function(stones) {
    const st = stones.slice();
    while (st.length > 1) {
        st.sort(function(a, b) { return a - b; });
        const y = st.pop(), x = st.pop();
        if (y !== x) st.push(y - x);
    }
    return st.length === 0 ? 0 : st[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy