Last Stone Weight

Problem Statement

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x less than or equal to y. The result of this smash is:

• If x equals y, both stones are destroyed
• If x does not equal y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x

At the end of the game, there is at most one stone left. Return the weight of the last remaining stone. If there are no stones left, return 0.

Examples

Example 1

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

Explanation:
Turn 1: Smash 8 and 7 → result = 1, stones = [2,4,1,1,1]
Turn 2: Smash 4 and 2 → result = 2, stones = [2,1,1,1]
Turn 3: Smash 2 and 1 → result = 1, stones = [1,1,1]
Turn 4: Smash 1 and 1 → result = 0, stones = [1]
Turn 5: Only one stone left, return 1

Example 2

Input: stones = [1]
Output: 1

Example 3

Input: stones = [2,2]
Output: 0

Explanation: Both stones are destroyed

Intuition

We need to repeatedly find the two largest elements, which naturally suggests using a max-heap!

Process:

1. Build max-heap from all stones
2. While heap has 2 or more stones:
   • Pop two largest stones (x, y)
   • If they differ, push (y - x) back
3. Return last stone (or 0 if empty)

Why heap? Finding max in unsorted array is O(n), but heap gives us max in O(log n) and maintains ordering automatically.

Pattern Recognition

This is a Max-Heap Simulation problem:

• Repeatedly extract maximum elements
• Process and potentially re-insert
• Continue until termination condition

Approach

Max-Heap Solution

Python Note: Python's heapq is a min-heap, so negate values to simulate max-heap.

1. Build Heap: Add all stones (negate for Python)
2. Simulate Game:

   while len(heap) > 1:
     first = heappop(heap)   # Largest
     second = heappop(heap)  # Second largest
     if first != second:
       heappush(heap, first - second)
   

3. Return Result: Last stone or 0

Java: Use PriorityQueue with reverse comparator for max-heap.

Edge Cases

• Single stone (return it)
• All stones same weight (return 0)
• Two stones (return difference or 0)
• Empty array
• Large weight values

Complexity Analysis

• Time: O(n log n) where n = number of stones

  • Build heap: O(n)
  • Each turn: 2 pops + 1 push = O(log n)
  • At most n-1 turns
  • Total: O(n log n)

• Space: O(n)

  • Store all stones in heap
  • In-place if modifying input allowed

Alternative: Sorting works but is O(n² log n) since we'd need to re-sort after each turn.