#65 Easy Time O(n log n) Space O(n) Animated

Last Stone Weight

Simulate smashing stones and return the last stone weight.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Priority queue for the next best choice

Keep only candidates that may become the next answer, ordered by the priority that matters.

Approach: Max-Heap

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Keep only candidates that may become the next answer, ordered by the priority that matters.

Common Pitfall

Push only meaningful candidates and remove stale entries before trusting the root.

Description

Simulate smashing stones and return the last stone weight.

Constraints

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

Solution — Max-Heap

TimeO(n log n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose the priority key.
Push initial candidates.
Pop the best valid candidate.
Add newly eligible candidates and repeat.

def lastStoneWeight(stones):
    stones = [-s for s in stones]
    heapq.heapify(stones)
    
    while len(stones) > 1:
        first = heapq.heappop(stones)
        second = heapq.heappop(stones)
        if second > first:
            heapq.heappush(stones, first - second)
            
    stones.append(0)
    return abs(stones[0])

Kth Largest Element in a Stream

K Closest Points to Origin

Last Stone Weight

Steps

Description

Constraints

Tags

Solution — Max-Heap