Last Stone Weight

Difficulty: Easy · Topic: Heaps

Each turn, take the two heaviest stones x ≥ y and smash them: if x == y both are destroyed, otherwise a stone of weight x - y remains. Return the weight of the last stone (or 0 if none remain). A max-heap gives the two heaviest in O(log n) each turn.

Examples

last_stone_weight([2,7,4,1,8,1])
→ 1

8,7→1; then 4,2→2; 2,1,1,1→ … → 1.

last_stone_weight([1])
→ 1

Target complexity: time O(n log n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.