#1046 Last Stone Weight

frequently reported atNVIDIA PayPal Amazon Salesforce Bloomberg Google

the problem

In plain words

Each turn, smash the two heaviest stones x ≤ y. Equal → both vanish; otherwise a stone of y − x remains. Return the last stone's weight, or 0 if none remain.

in stones = [2,7,4,1,8,1]

out 1

8,7→1; 4,2→2; 2,1→1; 1,1→0; last stone 1.

in stones = [1]

out 1

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGreedy with a heap

"Repeatedly take the two largest" while new values appear — that's a max-heap's job description.

solutions

From brute force to optimal

Sort the list, take the last two, put back the difference, repeat.

While > 1 stone: sort, remove two largest, add y − x if non-zero.

timeO(n² log n)

Up to n rounds, each sorting O(n log n).

spaceO(n)

The list.

javajava.util.*

1class Solution {2    public int lastStoneWeight(int[] stones) {3        List<Integer> list = new ArrayList<>();4        for (int s : stones) list.add(s);5        while (list.size() > 1) {6            Collections.sort(list);                       // O(n log n) every round7            int y = list.remove(list.size() - 1);         // heaviest8            int x = list.remove(list.size() - 1);         // second heaviest9            if (y != x) list.add(y - x);10        }11        return list.isEmpty() ? 0 : list.get(0);12    }13}

Poll the two heaviest, offer the leftover.

Offer all stones into a max-heap.
While size > 1: y = poll, x = poll; if y ≠ x offer y − x.
Return peek or 0.

timeO(n log n)

At most n rounds of O(log n) heap work.

spaceO(n)

The heap.

javajava.util.*

1class Solution {2    public int lastStoneWeight(int[] stones) {3        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());4        for (int s : stones) heap.offer(s);5        while (heap.size() > 1) {6            int y = heap.poll();                          // heaviest7            int x = heap.poll();                          // second heaviest8            if (y != x) heap.offer(y - x);                // the leftover goes back in9        }10        return heap.isEmpty() ? 0 : heap.peek();11    }12}

in the room

How to say it in the interview

talk track

Restate: each turn takes the two heaviest stones, and the leftover goes back into the pile.
Brute: sort every round and take the last two — O(n² log n).
Optimal: a max-heap, PriorityQueue with Comparator.reverseOrder(). Poll twice, offer y − x if it isn't 0.
Complexity: at most n − 1 rounds of O(log n) heap work, so O(n log n) time and O(n) space.
Test [1], [2, 2] (everything cancels → 0) and the sample [2,7,4,1,8,1] → 1.

traps

Using new PriorityQueue<>() — that's a min-heap in Java, so you smash the lightest stones.
Calling peek() on an empty heap at the end: it returns null, and unboxing it throws. Return 0 when it's empty.
Pushing back a 0 when the two stones are equal.

what they ask next

Follow-ups

Last Stone Weight II (LC 1049) — you choose any two stones?

Completely different: it becomes a subset-sum DP (split stones into two groups with sums as close as possible).

before you submit

Edge cases to test

One stone: return it.
Everything cancels, e.g. [2, 2]: return 0.
The two heaviest are equal: both vanish and nothing goes back.

practise next