Last Stone Weight

Problem in Plain English

You are given stone weights and repeatedly smash the two heaviest stones, keeping the difference when they differ and destroying both when they match. Return the last remaining weight, or 0 when no stones survive.

Problem Statement

Given an array of integers stones, where each entry is the weight of one stone, smash the stones together until at most one remains.

On each turn, pick the two heaviest stones with weights x and y where $x \le y$ . When both weights match, the two stones destroy each other; otherwise the lighter stone is destroyed and the heavier stone continues with weight $y - x$ .

Return the weight of the last remaining stone, or 0 when no stones are left.

Constraints

1 <= stones.length <= 30
1 <= stones[i] <= 1000

Examples

Example 1

Input: stones = [2,7,4,1,8,1]
Output: 1

Smash 8 and 7 into 1, then 4 and 2 into 2, then 2 and 1 into 1, then the two 1 stones destroy each other, leaving a single 1.

Example 2

Input: stones = [1]
Output: 1

There is only one stone, so no smash happens and its weight is the answer.

Example 3

Input: stones = [10,10,3]
Output: 3

The two heaviest stones both weigh 10, so both disappear. The remaining 3 survives without another smash. Equal weights are separate stones, so duplicates must not be collapsed.

Example 4

Input: stones = [2,2]
Output: 0

The only two stones have equal weights and both disappear. An empty pile returns 0; there is no surviving zero-weight stone.

Intuition

The rule fixes which pair to smash: always choose the two heaviest live stones, including any difference created earlier. In Example 1, 8 and 7 become 1, so the next pair is 4 and 2 rather than the next two original entries. We only need a collection that retains duplicate weights and repeatedly exposes its two largest values. Sorting provides a direct simulation; a max heap maintains just the ordering needed to get each maximum.

Approaches

Repeated Sorting

Solution Details

Reveal Repeated Sorting: intuition, complexity, and code

Intuition

Sorting the pile before every smash always exposes the two heaviest stones without any extra data structure. Re-sorting after each smash keeps that order correct, at the price of paying a full sort on every turn.

Step-by-Step Logic

Copy the input into a working pile so sorting and removals leave the caller's array unchanged. In Example 1 the copy starts as [2,7,4,1,8,1].
While at least two stones remain, sort the current pile in ascending numeric order. Its final two entries are the heaviest: Example 1 sorts to [1,1,2,4,7,8].
Remove the last entry as y, then the new last entry as x. If they differ, append y - x; if equal, append nothing. The first smash removes 8 and 7 and appends 1.
Repeat the sort after every smash because an appended difference can be out of order. The next pairs in Example 1 are 4 and 2, then 2 and 1, then 1 and 1.
Once fewer than two entries remain, return the sole weight or 0 for an empty pile. Example 1 leaves [1] and returns 1.

Why It Works

Before each iteration the working pile contains exactly the live stones, with duplicate weights retained as separate entries. Sorting changes their order but not their weights or multiplicities, so the last two entries are exactly the two heaviest required by the rule. Removing them and appending their positive difference, or appending nothing when equal, produces precisely the next live pile. This preserves the invariant from the initial copy onward. Each iteration removes at least one stone, so the loop terminates with at most one; its final weight, or 0 for an empty pile, is the required answer.

Dry Run

Repeated Sorting: variable states at each step
Round	Sorted pile before removal	`y`	`x`	Difference inserted	Pile after smash
Start	not sorted: `[2,7,4,1,8,1]`	—	—	—	6 stones
1	`[1,1,2,4,7,8]`	8	7	1	`[1,1,2,4,1]`
2	`[1,1,1,2,4]`	4	2	2	`[1,1,1,2]`
3	`[1,1,1,2]`	2	1	1	`[1,1,1]`
4	`[1,1,1]`	1	1	none; both destroyed	`[1]`
Return	`[1]` has fewer than 2 entries	—	—	—	return 1

Complexity Analysis

Time Complexity

O(n^2 \log n)

Space Complexity

O(n)

Let n be the initial number of stones. Each smash removes at least one entry, giving at most n - 1 rounds; sorting a current pile of at most n entries costs O(n log n), for an O(n² log n) upper bound. The working copy uses O(n) auxiliary space, including Java boxed integers; typical Java/Python/JavaScript sorting workspace is at most linear and does not change this bound. End removals are constant time and appends are amortized constant time. The scalar result uses O(1) space; the input is preserved.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4
5class Solution {6    public int lastStoneWeight(int[] stones) {7        List<Integer> pile = new ArrayList<>();8        for (int s : stones) pile.add(s);9        while (pile.size() > 1) {10            Collections.sort(pile);11            // Sorting again is necessary after appending an unordered difference.12            int y = pile.remove(pile.size() - 1);13            int x = pile.remove(pile.size() - 1);14            // Equal stones disappear; do not create a zero-weight stone.15            if (y > x) pile.add(y - x);16        }17        return pile.isEmpty() ? 0 : pile.get(0);18    }19}

Hints

Hint 1

Follow the exact simulation: a new difference participates in choosing the next two heaviest stones.

Hint 2

Sorting the current pile on every round exposes the two largest entries, but repeats work.

Hint 3

A max heap returns the heaviest live stone with each pop in

O(\log n)

time. For portable Python code, use a min heap of negative weights.

Edge Cases

A single stone such as [1] needs no smash, so the answer is that stone itself.
Two equal stones such as [2, 2] destroy each other and leave an empty pile, so return 0 and never index into the empty heap.
Equal pairs late in the game, like the three 1 stones in Example 1, can shrink the pile by two at once without pushing anything back.
Two unequal stones such as [1,1000] leave 999, which needs no further smash.
Thirty identical maximum-weight stones all cancel in pairs; an odd number of identical stones leaves one.

Common Mistakes and Interview Tips

Selecting stones from the original sorted order after a smash: the difference must compete with all remaining stones.
Treating equal weights as one set entry loses separate stones and breaks cancellation.
Using JavaScript's default sort compares strings; use (a, b) => a - b for numeric weights.
Mixing negated heap entries and real weights in Python subtraction. Convert both popped values back, then negate a surviving difference on insertion.
Reading the top of an empty heap after equal stones destroy each other; guard the final return.
Interview tip: inserting a zero for an equal pair models a nonexistent stone. It needlessly retains entries, even though with nonnegative weights the final numeric answer may still be unchanged.

Key Takeaway

Whenever a simulation repeatedly needs the largest or smallest live element, a heap replaces each linear scan or full sort with a logarithmic pop and push.