Last Stone Weight

Problem

https://leetcode.com/problems/last-stone-weight/

You are given an array of integers stones where stones[i] is the weight of the i:sup:`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

  • 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. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

  • 1 <= stones.length <= 30

  • 1 <= stones[i] <= 1000

Pattern

Array, Heap (Priority Queue)

Approaches

Explanation

To play the game, we need to repeatedly find the two heaviest stones. A max heap is a data structure that us to efficiently retrieve and remove the largest element. We put all the stones into a max heap, then repeatedly pop the two largest stones, smash them together, and push the remaining stone back into the heap if there is one, continuing until there is at most one stone left in the heap.

Code

import heapq


def lastStoneWeight(stones: list[int]) -> int:
    """Return the weight of the last remaining stone."""
    heap = list(stones)
    heapq.heapify_max(heap)
    while len(heap) > 1:
        y = heapq.heappop_max(heap)
        x = heapq.heappop_max(heap)
        if x != y:
            heapq.heappush_max(heap, y - x)
    return heap[0] if heap else 0

Test

>>> from last_stone_weight__max_heap import lastStoneWeight
>>> lastStoneWeight([2, 7, 4, 1, 8, 1])
1
>>> lastStoneWeight([1])
1

Complexity

\(n\) is the number of stones.

Measure

Complexity

Notes

Time

\(O(n \log n)\)

heapify is \(O(n)\), then \(O(n)\) pops/pushes which are \(O(\log n)\) each

Auxiliary Space

\(O(n)\)

the heap
last_stone_weight__max_heap.lastStoneWeight(stones: list[int]) → int

Return the weight of the last remaining stone.