Last Stone Weight

Last Stone Weight

1. What is this problem about?

The Last Stone Weight coding problem simulates a game played with stones. Each stone has a positive integer weight. In each turn, you pick the two heaviest stones and smash them together. If the stones have the same weight, both are destroyed. If they have different weights, the smaller one is destroyed, and a new stone with the weight difference is added back. You repeat this until at most one stone remains.

2. Why is this asked in interviews?

This "Easy" problem is a staple at top companies like Microsoft, Meta, and Nvidia because it perfectly illustrates the use of a Priority Queue. It tests a candidate's ability to identify when a data structure can simplify a repetitive "find maximum" task. Interviewers use it to gauge your familiarity with heaps and your ability to implement a simple simulation efficiently.

3. Algorithmic pattern used

This problem follows the Heap (Priority Queue) interview pattern. To always pick the two heaviest stones, we use a Max-Heap. We push all stone weights into the Max-Heap. In a loop, we extract the two largest elements, calculate their difference, and if the difference is greater than zero, we push it back into the heap. This continues until the heap has 0 or 1 element.

4. Example explanation

Stones: [2, 4, 1, 1].

1. Max-Heap: [4, 2, 1, 1].
2. Smash 4 and 2. Difference is 2.
3. New Heap: [2, 1, 1].
4. Smash 2 and 1. Difference is 1.
5. New Heap: [1, 1].
6. Smash 1 and 1. Both destroyed.
7. Final Stone: 0 (or no stones). Result: 0.

5. Common mistakes candidates make

A common mistake is sorting the array in every iteration, which leads to O(N² log N) complexity. Using a Max-Heap reduces this to O(N log N). Another error is not correctly handling the case where only one stone or no stones are left in the heap at the end. Some candidates also forget that many languages (like Python) implement a Min-Heap by default, so you must negate the values to simulate a Max-Heap.

6. Interview preparation tip

When a problem requires you to repeatedly find and remove the largest (or smallest) element while adding new elements back, a "Heap, Priority Queue interview pattern" is almost always the optimal choice. Master the heap push and pop operations in your favorite language.