Last Stone Weight

Easy·Tagsheappriority-queuesimulation

Problem Statement

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 neither is added back. * If `x != y`, the stone of weight `x` is destroyed, and the stone of weight `y` has a new weight of `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"

Why

We combine 7 and 8 to get 1 so the array converts to [2, 4, 1, 1, 1]. We combine 2 and 4 to get 2 so the array converts to [2, 1, 1, 1]. We combine 2 and 1 to get 1 so the array converts to [1, 1, 1]. We combine 1 and 1 to get 0 so the array converts to [1]. The last remaining stone has a weight of 1.

Example 2

Input

stones: [1]

Output

"1"

Why

There is only one stone, so we return its weight immediately.

Constraints

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

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

The problem strictly asks us to process the 'heaviest' two stones repeatedly. This is a massive clue to use a specific data structure.

Hint 2

If we sort the array, finding the heaviest two stones is easy (the last two elements). But after we smash them and get a remainder, we have to insert that remainder back into the sorted array, which takes O(N) time.

Hint 3

Instead of sorting the whole array repeatedly, what if we used a Max-Heap? A Max-Heap guarantees the heaviest element is always at the top in O(1) time.

Hint 4

Pop the top element (y). Pop the next top element (x). If y > x, push (y - x) back into the Max-Heap. Repeat this until the heap has 1 or 0 elements left.