Last Stone Weight 15 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

You have a collection of stones with weights. Each turn, smash the two heaviest stones together:

If they're equal weight → both destroyed
If different → the lighter one is destroyed, the heavier one's weight becomes the difference

stones = [2, 7, 4, 1, 8, 1]
# Smash 8 and 7 → 8-7=1 remains → [2, 4, 1, 1, 1]
# Smash 4 and 2 → 4-2=2 remains → [1, 1, 1, 2]
# Smash 2 and 1 → 2-1=1 remains → [1, 1, 1]
# Smash 1 and 1 → destroyed → [1]
# Answer: 1

This screams max-heap! We need to repeatedly get the two largest elements. Since Python only has min-heap, negate the values:

# Max-heap trick: push -weight, pop gives -largest
heapq.heappush(heap, -8)  # internally [-8, ...]
val = -heapq.heappop(heap)  # val = 8

📋 Instructions

Implement `last_stone_weight(stones)` using a max-heap (negated min-heap). Return the weight of the last remaining stone, or 0.

Negate all values and heapify. While len(heap) > 1: pop two largest (negate back). If different, push -(abs(a) - abs(b)). Return -heap[0] if heap else 0.

🧪 Test Cases

Input

last_stone_weight([2, 7, 4, 1, 8, 1])

Expected

1

Test case 1

Input

last_stone_weight([1])

Expected

1

Edge case — single element

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›