Last Stone Weight

Estimated reading: 4 minutes 37 views

Question

You are given an array of integers stones where stones[i] is the weight of the i^th 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 <= y. The result of this smash is:

If x == y, both stones are destroyed, and
If x != 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.

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

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

Code

				
					 public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int s : stones) {
            minHeap.offer(-s);
        }

        while (minHeap.size() > 1) {
            int first = minHeap.poll();
            int second = minHeap.poll();
            if (second > first) {
                minHeap.offer(first - second);
            }
        }

        minHeap.offer(0);
        return Math.abs(minHeap.peek());
    }

Convert All Weights to Negative:

				
					for (int s : stones) {
    minHeap.offer(-s);
}

We iterate over each stone in the array stones and insert its negative value into the minHeap. By storing negative weights, the min-heap will effectively behave like a max-heap, because the smallest value in a min-heap will correspond to the largest (positive) stone weight.

Smash the Two Heaviest Stones

				
					while (minHeap.size() > 1) {
    int first = minHeap.poll();
    int second = minHeap.poll();
    if (second > first) {
        minHeap.offer(first - second);
    }
}

The loop continues until there is one or zero stones left in the heap.
In each iteration, the two heaviest stones (i.e., the two smallest negative numbers in the heap) are removed using minHeap.poll().
- first and second represent the two heaviest stones (in negative values).
If the stones have different weights (i.e., second > first), the difference between their negative values (first - second) is added back to the heap, which simulates keeping the remaining weight after smashing.

Handle the Remaining Stone

				
					minHeap.offer(0);
return Math.abs(minHeap.peek());

If no stones are left, the heap will be empty, so we add 0 to the heap as a fallback in case there are no remaining stones.
The method then returns the absolute value of the top element in the heap (minHeap.peek()), which will either be the weight of the last stone or 0.

Example Walkthrough:

Let’s take an example:

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

We push negative values into the heap: [-2, -7, -4, -1, -8, -1].
- Heap (max-heap simulated with negatives): [-8, -7, -4, -1, -2, -1]
First iteration:
- Poll the two heaviest stones (-8, -7) → Original weights are 8 and 7.
- Smash them: 8 - 7 = 1 → Add -1 back to the heap.
- Heap: [-4, -2, -1, -1, -1]
Second iteration:
- Poll the two heaviest stones (-4, -2) → Original weights are 4 and 2.
- Smash them: 4 - 2 = 2 → Add -2 back to the heap.
- Heap: [-2, -1, -1, -1]
Third iteration:
- Poll the two heaviest stones (-2, -1) → Original weights are 2 and 1.
- Smash them: 2 - 1 = 1 → Add -1 back to the heap.
- Heap: [-1, -1, -1]
Fourth iteration:
- Poll the two heaviest stones (-1, -1) → Original weights are 1 and 1.
- Both stones are destroyed since they are equal, so no new stone is added back.
- Heap: [-1]
Final:
- Only one stone remains, so the loop exits.
- Return the absolute value of the last stone: | -1 | = 1.

Summary of Key Operations:

The min-heap is used to simulate a max-heap by storing negative weights.
The two heaviest stones are repeatedly smashed together, and if one remains, it is added back to the heap.
The process continues until one or no stones remain, and the result is the weight of the last remaining stone (or 0 if none).