LeetCode 1046: Last Stone Weight

Problem Restatement

We have a collection of stones, each with a positive weight.

In each round, we smash the two heaviest stones together:

• If equal: both are destroyed.
• If not equal: the lighter is destroyed and the heavier remains with weight heavier - lighter.

We repeat until at most one stone is left.

Return the weight of the last stone, or 0 if none remain.

The official constraints state that 1 <= stones.length <= 30 and 1 <= stones[i] <= 1000.

Input and Output

Function shape:

def lastStoneWeight(stones: list[int]) -> int:
    ...

Examples

Example 1:

stones = [2, 7, 4, 1, 8, 1]

Smash 8 and 7 → 1. Stones: [2, 4, 1, 1, 1].

Smash 4 and 2 → 2. Stones: [2, 1, 1, 1].

Smash 2 and 1 → 1. Stones: [1, 1, 1].

Smash 1 and 1 → 0. Stones: [1].

Answer:

1

Key Insight

We always need the two largest stones. A max heap gives O(log n) access to the largest element.

Python’s heapq is a min-heap, so negate all values to simulate a max heap.

Algorithm

1. Push all negated stone weights onto a min heap.
2. While the heap has more than one element:
   • Pop two largest weights.
   • If not equal, push back the difference (negated).
3. Return the remaining weight, or 0 if heap is empty.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)

        while len(heap) > 1:
            a = -heapq.heappop(heap)
            b = -heapq.heappop(heap)
            if a != b:
                heapq.heappush(heap, -(a - b))

        return -heap[0] if heap else 0

Testing

def run_tests():
    s = Solution()

    assert s.lastStoneWeight([2, 7, 4, 1, 8, 1]) == 1
    assert s.lastStoneWeight([1]) == 1
    assert s.lastStoneWeight([2, 2]) == 0
    assert s.lastStoneWeight([3, 7, 2]) == 2

    print("all tests passed")

run_tests()