1046. Last Stone Weight - Detailed Explanation

Problem Statement

You’re given an array of positive integers stones, where each element represents the weight of a stone. You play the following game until there is at most one stone left:

Choose the two heaviest stones, with weights x and y (x ≤ y).
Smash them together:
- If x == y, both stones are destroyed.
- If x != y, the lighter stone x is destroyed and the heavier stone’s weight becomes y - x, which is inserted back into the collection.
  Return the weight of the remaining stone (or 0 if no stones remain).

Examples

Example 1

Input   stones = [2,7,4,1,8,1]
Output  1
Explanation  
  - Smash 7 and 8 → new stone of weight 1, stones become [2,4,1,1,1]  
  - Smash 1 and 2 → new stone of weight 1, stones become [4,1,1,1]  
  - Smash 1 and 4 → new stone of weight 3, stones become [3,1,1]  
  - Smash 1 and 3 → new stone of weight 2, stones become [2,1]  
  - Smash 1 and 2 → new stone of weight 1, stones become [1]  
  - Only one stone remains, weight = 1

Example 2

Input   stones = [1]
Output  1
Explanation  Only one stone, no smash needed.

Constraints

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

Hints

How can you efficiently retrieve and remove the two largest elements repeatedly?
What data structure supports repeated extraction of the maximum?
Could you sort every time instead—and what would that cost?

Approach 1 – Repeated Sorting (Brute Force)

Idea

At each step, sort the array in descending order, pick the first two elements, smash them, update the array, and repeat until ≤1 stone remains.

Steps

While stones.length > 1:
- Sort stones in non‑increasing order.
- Let x = stones[0], y = stones[1].
- Remove both from the array.
- If x != y, append x - y back into stones.
If the array is empty return 0; otherwise return stones[0].

Code (Python)

Python3

. . . .

Code (Java)

Java

. . . .

Complexity Analysis

Sorting each iteration takes O(n log n), and in the worst case you do up to n‑1 smashes → O(n² log n).
Space: O(n) for the working list.

Approach 2 – Max‐Heap (Priority Queue)

Idea

Maintain a max‐heap so you can extract the two largest stones in O(log n) each time, then push back the smash result if nonzero in O(log n).

Steps

Build a max‐heap (in Python, use a min‐heap of negatives).
While heap size > 1:
- Pop the two largest stones y and x (so y ≥ x).
- If y != x, push back y - x.
If heap is empty return 0 else return the remaining stone.

Code (Python)

Python3

. . . .

Code (Java)

Java

. . . .

Complexity Analysis

Heap construction: O(n)
Each smash: two pops + optional push → O(log n) each
Up to n−1 smashes → O(n log n) total
Space: O(n) for the heap

Step‑by‑Step Walkthrough

Take stones = [2,7,4,1,8,1] and max‑heap approach:

Heapify → [8,7,4,1,2,1]
Pop 8 and 7 → smash → push 1 → heap now [4,2,1,1,1]
Pop 4 and 2 → smash → push 2 → heap [2,1,1,1]
Pop 2 and 1 → smash → push 1 → heap [1,1,1]
Pop 1 and 1 → smash → equal → push nothing → heap [1]
Only one stone remains → return 1

Common Mistakes

Using a min‑heap without negation in Python.
Forgetting to push back the difference when stones differ.
Mixing up which stone is subtracted from which (y - x must be nonnegative).
Off‑by‑one: stopping when heap size < 2 too early.

Edge Cases

Single stone → return its weight.
All stones same weight → all cancel → return 0.
Two stones → either return 0 (if equal) or their difference.

Alternative Variations

Last Stone Weight II (LeetCode 1049): partition into two groups to minimize the final weight.
Multi‑smash: smash the k heaviest stones at once.
Weighted smash: difference is some function f(x,y) instead of absolute difference.