65.Last Stone Weight

EasyHeap / Priority Queue · 2/7

Problem

You have an array stones where stones[i] is the weight of the i-th stone. Each turn, take the two heaviest stones x <= y and smash them:

If x == y, both are destroyed.
If x != y, x is destroyed and y becomes y - x.

Repeat until at most one stone remains. Return its weight, or 0 if none remain.

Examples

Input:  stones = [2,7,4,1,8,1]
Output: 1
Explanation: smash 7,8 -> 1 => [2,4,1,1,1]; smash 2,4 -> 2 => [2,1,1,1];
             smash 2,1 -> 1 => [1,1,1]; smash 1,1 -> 0 => [1]. Answer 1.

Input:  stones = [1]
Output: 1

Input:  stones = [3,3]
Output: 0
Explanation: Equal stones destroy each other.

Constraints

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

💡 Key Insight

Every turn needs the current two largest values, and the remainder y - x is put back into the pool. A max-heap supports exactly that: two polls and at most one offer, each O(log n), instead of re-sorting the whole array every turn.

Brute Force (Sort Every Turn)

TimeO(n² log n)SpaceO(n)

Intuition

Keep the stones in a list, sort it each turn, and take the last two. Simulate literally.

Algorithm

Put the stones into a list.
While the list has more than one stone: sort it, remove the last two y and x, and if y != x add y - x.
Return the remaining stone or 0.

Visualization

[2,7,4,1,8,1] sort -> [1,1,2,4,7,8] take 8,7 -> add 1
[1,1,2,4,1]   sort -> [1,1,1,2,4]   take 4,2 -> add 2
[1,1,1,2]     sort -> [1,1,1,2]     take 2,1 -> add 1
[1,1,1]                             take 1,1 -> nothing
[1] -> 1

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> list = new ArrayList<>();
        for (int s : stones) {
            list.add(s);
        }
        while (list.size() > 1) {
            Collections.sort(list);
            int y = list.remove(list.size() - 1); // heaviest
            int x = list.remove(list.size() - 1); // second heaviest
            if (y != x) {
                list.add(y - x);
            }
        }
        return list.isEmpty() ? 0 : list.get(0);
    }
}

Complexity

Time: O(n² log n) — up to n turns, each with an O(n log n) sort.
Space: O(n) — the list.

Sorted List with Binary Insertion

TimeO(n²)SpaceO(n).

Intuition

Sort once. After removing the two largest from the end, the remainder must go back in sorted position — binary-search that spot instead of re-sorting.

Algorithm

Sort the stones into a list.
While size > 1: remove the last two; if diff = y - x > 0, binary-search the first index with value >= diff and insert there.
Return the remaining stone or 0.

Visualization

sorted = [1,1,2,4,7,8]
remove 8,7 -> diff 1 -> insert at index 0 -> [1,1,1,2,4]
remove 4,2 -> diff 2 -> insert at index 3 -> [1,1,1,2]

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> list = new ArrayList<>();
        for (int s : stones) {
            list.add(s);
        }
        Collections.sort(list);
        while (list.size() > 1) {
            int y = list.remove(list.size() - 1);
            int x = list.remove(list.size() - 1);
            int diff = y - x;
            if (diff > 0) {
                int lo = 0, hi = list.size();
                while (lo < hi) { // first index with value >= diff
                    int mid = (lo + hi) >>> 1;
                    if (list.get(mid) < diff) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                list.add(lo, diff);
            }
        }
        return list.isEmpty() ? 0 : list.get(0);
    }
}

Complexity

Time: O(n²) — n turns, each with an O(n) insertion shift (search is O(log n)).
Space: O(n).

Max-HeapOptimal

TimeO(n log n)SpaceO(n)

Intuition

A max-heap always exposes the heaviest stone. Poll twice to get y and x, push back y - x if non-zero. The heap re-orders itself in O(log n).

Algorithm

Push every stone into a PriorityQueue with Collections.reverseOrder().
While heap.size() > 1: y = poll(), x = poll(); if y > x offer y - x.
Return heap.isEmpty() ? 0 : heap.peek().

Dry Run

flowchart TD
    A["heap = {8,7,4,2,1,1}"] -->|"poll 8, 7 -> push 1"| B["heap = {4,2,1,1,1}"]
    B -->|"poll 4, 2 -> push 2"| C["heap = {2,1,1,1}"]
    C -->|"poll 2, 1 -> push 1"| D["heap = {1,1,1}"]
    D -->|"poll 1, 1 -> equal, push nothing"| E["heap = {1}"]
    E --> F["return 1"]

Code

java

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) {
            maxHeap.offer(s);
        }
        while (maxHeap.size() > 1) {
            int y = maxHeap.poll(); // heaviest
            int x = maxHeap.poll(); // second heaviest
            if (y > x) {
                maxHeap.offer(y - x); // survivor goes back
            }
        }
        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

Complexity

Time: O(n log n) — building the heap plus at most n - 1 turns of O(log n) work.
Space: O(n) — the heap.

Complexity Comparison

Approach	Time	Space
Sort Every Turn	O(n² log n)	O(n)
Sorted List + Binary Insertion	O(n²)	O(n)
Max-Heap	O(n log n)	O(n)

Common Pitfalls

Using Java's default PriorityQueue, which is a min-heap — you would smash the two lightest stones.
Returning heap.peek() without checking for an empty heap (all stones may cancel out, e.g. [3,3]).
Pushing 0 back when the stones are equal — harmless for the answer but wrong semantics and extra turns; only push when y > x.
Computing x - y (negative) after polling in the wrong order.