Last Stone Weight (LC 1046)

Pattern: Max-Heap / Greedy with Heap
Difficulty: Easy
Key Concept: Repeatedly take the two heaviest stones using a max-heap; smash and push back the remainder until at most one stone remains.

Problem Statement

You have an array stones where stones[i] is the weight of the i-th stone.

Each turn:

1. Choose the two heaviest stones (weights x and y with x <= y).
2. Smash them together:
   • If x == y, both are destroyed.
   • If x != y, the stone of weight y is destroyed, and the stone of weight x becomes y - x.

Repeat until there is at most one stone left.

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

Input

• int[] stones — positive weights.

Output

• int — last stone’s weight, or 0.

Constraints (typical)

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

---

1. Algorithm & Pseudocode

Brute force (sort every turn)

while more than one stone:
  sort stones descending
  y = stones[0]   // heaviest
  x = stones[1]   // second heaviest
  remove both from structure
  if y > x:
    insert (y - x) back

if one stone left: return it
else: return 0

Optimal (max-heap)

pq = max-heap of all stone weights

while pq.size() > 1:
  y = pq.poll()   // largest
  x = pq.poll()   // second largest
  if y > x:
    pq.offer(y - x)

if pq is empty: return 0
else: return pq.poll()

Why this works
Each turn only the relative order of the two largest matters; a max-heap gives O(log n) access to the top two weights without re-sorting the whole array.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why always the two heaviest?
   The problem statement fixes the rule: every turn uses the maximum and second maximum remaining. Any solution must simulate that exactly.

2. Why not sort once and merge?
   After a smash, you insert a new weight (y - x). The global order changes; you need a dynamic structure that can repeatedly extract maxima.

3. Max-heap vs min-heap
   Java’s PriorityQueue is a min-heap. For “largest first,” use Collections.reverseOrder() or a comparator that orders descending. Conceptually you want “poll = heaviest.”

4. Comparator safety: b - a vs Integer.compare(b, a)
   Subtracting can overflow for large int values (not in LeetCode’s tiny constraints here, but good habit). Integer.compare(b, a) compares without arithmetic overflow.

5. When do we push y - x?
   Only when y > x. If y == x, both disappear—nothing to push. If y < x, that cannot happen if y is the max and x the second max (so y >= x always).

6. Loop until size ≤ 1
   With one stone, that is the answer. With zero stones, return 0.

---

3. The Dry Run

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

We trace the multiset of weights after each turn. The max-heap implements “always take two largest”; poll order is largest first, then second largest.

Turn	Stone count	Weights sorted (desc)	First poll y	Second poll x	Smash	New weight pushed?	Weights after (desc)
—	6	8, 7, 4, 2, 1, 1	—	—	—	—	(initial)
1	6 → 5	8, 7, 4, 2, 1, 1	8	7	8 - 7 = 1	yes: 1	4, 2, 1, 1, 1
2	5 → 4	4, 2, 1, 1, 1	4	2	4 - 2 = 2	yes: 2	2, 1, 1, 1
3	4 → 3	2, 1, 1, 1	2	1	2 - 1 = 1	yes: 1	1, 1, 1
4	3 → 1	1, 1, 1	1	1	equal → both gone	no	1
5	1	1	—	—	stop (size ≤ 1)	—	1

Final answer: 1.

Heap operations only (compact trace)

Turn	poll (1st)	poll (2nd)	offer
1	8	7	1
2	4	2	2
3	2	1	1
4	1	1	—
done	—	—	return 1

---

4. Java Solution

Brute Force

Idea: Use a list, sort descending each turn, remove two largest, insert difference if needed.

Time: O(n^2 log n) in the worst case (up to O(n) turns, each sort O(n log n)). Space: O(n).

import java.util.*;

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

Optimal

Time: O(n log n) for heap build plus O(n) iterations with O(log n) heap work → O(n log n) overall. Space: O(n).

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

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int w : stones) {
            pq.offer(w);
        }
        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();
            if (y > x) {
                pq.offer(y - x);
            }
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

Safer comparator (overflow-aware):

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

---

5. The “Java vs. Others” Edge

• Java: PriorityQueue + Collections.reverseOrder() gives a max-heap without negating integers (Python’s heapq is min-only, so you often negate weights).
• C++: std::priority_queue<int> is already a max-heap—same idea, opposite default vs Java.
• Avoid (a, b) -> b - a for general int weights: subtraction can overflow; prefer Integer.compare(b, a).
• poll() vs peek(): After the loop, use peek() or poll() once; check isEmpty() before returning 0.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n^2 log n) worst case	O(n)	Re-sort each turn; educational only.
Optimal	O(n log n)	O(n)	Max-heap; each smash does heap ops in O(log n).