9.6 Last Stone Weight

9.6.1 Problem Metadata

9.6.2 Description

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

On each turn, we choose the two heaviest stones and smash them together. Suppose the heaviest two stones have weights x and y with \(x \le y\). The result of this smash is:

  • If \(x = y\), both stones are destroyed.
  • If \(x \ne y\), the stone of weight x is destroyed, and the stone of weight y becomes 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.

9.6.3 Examples

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
- Smash 7 and 8, result is 1, stones = [2,4,1,1,1]
- Smash 2 and 4, result is 2, stones = [2,1,1,1]
- Smash 2 and 1, result is 1, stones = [1,1,1]
- Smash 1 and 1, result is 0, stones = [1]
- Last remaining stone has weight 1

9.6.4 Constraints

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

9.6.5 Solution - Max Heap

9.6.5.1 Walkthrough

Push all stones into a max heap. Repeatedly extract the two heaviest stones y (largest) and x (second largest). If they differ, push y - x back. Repeat until at most one stone remains.

9.6.5.2 Analysis

  • Time Complexity: O(n log n) — each of the n stones is pushed once and each heap operation costs O(log n)
  • Space Complexity: O(n) for the heap

9.6.5.3 Implementation Steps

  1. Push all stones into a max heap.
  2. While the heap has more than one element, poll the two heaviest stones y and x.
  3. If \(x \ne y\), push y - x back into the heap.
  4. Return the remaining element, or 0 if the heap is empty.

9.6.5.4 Code - Java

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();
        int x = maxHeap.poll();
        if (x != y) {
            maxHeap.offer(y - x);
        }
    }

    return maxHeap.isEmpty() ? 0 : maxHeap.peek();
}