< Back




1046. Last Stone Weight

Given a list of stones, we're asked to smash the heaviest two stones together at each step. If the
stones weight the same, they're both destroyed. If stone x < y, then stone y - x is left. We return
the remaining stone weight or 0 if no stones are left.

Using a heap, we can maintain the largest stones at the top of the heap. We can then pop the two
largest stones, smash them together, and push the remaining stone back into the heap. We continue
this process until there's only one stone left.

The solution is as follows:


  from heapq import *

  class Solution:
      def lastStoneWeight(self, stones: List[int]) -> int:
          stones = [-stone for stone in stones]
          heapify(stones)
          n = len(stones)

          while n > 1:
              y, x = -heappop(stones), -heappop(stones)
              n -= 2

              if x != y:
                  n += 1
                  heappush(stones, -(y - x))

          return 0 if not n else -heappop(stones)


_ Time Complexity:

  O(n log n) - We conduct at most n steps, and heap operations take at most log n time.

_ Space Complexity:

  O(n) - We store all the stones in the heap.