loading

Last Stone Weight — Step-by-Step Visualization

easyLeetCode #1046ArrayHeap (Priority Queue)

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`. If `x == y`, both stones are destroyed. 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 (or 0 if there are no stones left).

Algorithm Pattern

Max-Heap Simulation

Key Idea

To efficiently find the two largest values repeatedly, we can use a Max-Heap (Priority Queue). Each 'smash' operation involves two `pop` operations (O(log N)) and one potential `push` operation (O(log N)). The heap ensures the largest stones are always at the root.

Step-by-Step Approach

  1. Convert the initial array into a Max-Heap.
  2. While there is more than one stone in the heap:
  3. Pop the two largest stones, `y` and `x` (where `y >= x`).
  4. If `x != y`, push the difference `y - x` back into the heap.
  5. If `x == y`, both are destroyed; do nothing.
  6. Return the last stone in the heap, or 0 if it's empty.

Common Gotchas

  • In a Max-Heap, the parent is always greater than or equal to its children.
  • JavaScript doesn't have a built-in Heap, so we simulate the heap property manually on an array.

Related Problems

← All problems