Search⌘ K
AI Features

Problem: Last Stone Weight

Explore how to use a max heap to solve the last stone weight problem by repeatedly smashing the two heaviest stones until one or none remain. Understand heap operations and implement an efficient solution in Python with optimal time and space complexity.

Statement

You are given an integer array stones, where each element stones[i] represents the weight of the ithi^{th} stone.

A game is played with these stones. In each turn, the two heaviest stones are selected and smashed together. Let the weights of these two stones be x and y, where x \leq y. The outcome of the smash is as follows:

  • If x == y, both stones are completely destroyed.

  • If x \neq y, the stone of weight x is destroyed, and the stone of weight y is reduced to a new weight of y - ...