Easy — Heap | Priority Queue | Array | Simulation

The Problem

Given an array of stone weights, repeatedly smash the two heaviest stones together until at most one stone remains, returning the weight of the last stone or 0 if no stones remain.

Approach

Use a max-heap to efficiently find the two heaviest stones at each step. Since Python’s heapq implements a min-heap, we store negative values to simulate a max-heap. Extract the two largest stones, and if their weights differ, push the difference back into the heap.

Time: O(n log n) · Space: O(n)

Code

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        max_heap = [-stone for stone in stones]  # Use negative values for max-heap

        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            x = -heapq.heappop(max_heap)  # Extract the largest stone
            y = -heapq.heappop(max_heap)  # Extract the second largest stone

            if x != y:
                heapq.heappush(max_heap, -(x - y))  # Push the remaining weight

        return -max_heap[0] if max_heap else 0

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment