DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Last Stone Weight - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Python's heapq module only supports min-heaps by default. So, convert the list into a max-heap by negating the values.
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            first_stone = -heapq.heappop(max_heap)
            second_stone = -heapq.heappop(max_heap)
            if first_stone != second_stone:
                heapq.heappush(max_heap, -(first_stone - second_stone))
        return -max_heap[0] if max_heap else 0

Complexity Analysis

  • Time Complexity: O(n log n)
    Each insertion and removal from the heap takes O(log n) time, and we may do this up to n times. So, the total time complexity becomes O(n log n).
  • Space Complexity: O(n) extra space is used for storing the heap.

Here, n is the number of stones in the input.