Problem Statement in English

You’re given a list of stone weights - stones. Your task is to keep picking the 2 largest stones from that list, and smash them together until there’s either only 1 or no stones left, whilst following a few rules:

  • if the 2 stones have the same weight, then they’re both destroyed.
  • if the 2 stones have different weights, then you’re left with a stone that weighs the difference between the bigger and smaller one.

Approach

We need to maintain the stone weights in a max heap. That way, the 2 largest stones will always be at the top of the max heap.

Solution in Python


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i in range(len(stones)):
            stones[i] *= -1
        heapq.heapify(stones)

        while len(stones) > 1:
            s1 = heapq.heappop(stones)
            s2 = heapq.heappop(stones)

            if s1 != s2:
                heapq.heappush(stones, -abs(-s1 - -s2))

        return -stones[0] if len(stones) == 1 else 0

Unfortunately, the nasty method to maintain the max heap makes the code a little ugly. We need to multiply all elements by $-1$ to have Python build a max heap instead of a min heap.

Complexity

  • Time: $O(n)$
    As that’s the time taken to build the max heap for $n$ elements.

  • Space: $O(n)$
    As we store $n$ stone weights at most in the max heap.

And we are done.