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:

1. Choose the two heaviest stones, with weights x and y (x ≤ y).
2. 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

1. How can you efficiently retrieve and remove the two largest elements repeatedly?
2. What data structure supports repeated extraction of the maximum?
3. 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

1. 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.
2. If the array is empty return 0; otherwise return stones[0].

Code (Python)