Last Stone Weight — LeetCode 1046 Python Solution

The problem

You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones.

Example

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,

Python solution

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        h = [-x for x in stones]
        heapify(h)
        while len(h) > 1:
            y, x = -heappop(h), -heappop(h)
            if x != y:
                heappush(h, x - y)
        return 0 if not h else -h[0]

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1046. Last Stone Weight is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems