Developers

Last Stone Weight

EasyHeap and top-KAlso known as LeetCode 1046

You are given an array stones, where stones[i] is the weight of the i-th stone. Each turn, choose the two heaviest stones and smash them together. Say the weights are 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 now has weight y - x.

The game ends when at most one stone is left. Return the weight of the last remaining stone, or 0 if no stones remain.

Examples

Input stones = [2, 7, 4, 1, 8, 1]
Output 1
8 and 7 leave 1; 4 and 2 leave 2; 2 and 1 leave 1; 1 and 1 vanish; one stone of weight 1 remains.
Input stones = [1]
Output 1
Input stones = [3, 3]
Output 0
Equal stones destroy each other.

Constraints

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1,000

Stuck? Take one hint at a time

Common mistakes
  • Using a min-heap and forgetting to negate the values, so the two lightest stones are smashed.
  • Pushing the difference when it is 0, which leaves phantom stones of weight 0 in the game.
  • Subtracting in the wrong order, and getting a negative weight.
  • Reading the top of an empty heap when all stones were destroyed. Return 0 in that case.
  • Sorting once at the start and not again, even though the difference can land anywhere in the order.
Questions an interviewer may ask next
  • The stones can be very many and very heavy. What is the running time of the heap version, and what is its memory?
  • Weights are small integers (at most 1,000). Can you avoid the heap? (A counting array indexed by weight, scanning from the top.)
  • Instead of the two heaviest, smash the heaviest with the lightest. How does the answer change, and does the data structure change?
  • Return the sequence of smashes as well as the final weight.