LeetCode · #1046

Last Stone Weight Solution

Smash the two heaviest stones together repeatedly. If they differ, the remainder stays. Return the weight of the last remaining stone, or 0 if none.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #1046

🏗️

Pattern

Heap — simulation with max-heap

You have a collection of stones with positive integer weights. Each turn, pick the two heaviest stones and smash them. If they're equal, both are destroyed. If not, the lighter one is destroyed and the heavier one's weight is reduced by the lighter's weight. Return the weight of the last stone, or 0 if no stones remain.

Example

 Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1 // Smash 8,7→1. Smash 4,2→2. Smash 2,1→1. Smash 1,1→0. Last stone: 1. 

Constraints

• 1 ≤ stones.length ≤ 30 • 1 ≤ stones[i] ≤ 1000

Section Two · Approach 1

Brute Force — Sort Every Turn O(n² log n)

Sort the array each turn, take the last two elements (heaviest), smash them, and insert the remainder back. Repeat until one or zero stones remain.

Why it works

Sorting always places the two heaviest at the end. Correct by simulation — we follow the problem's exact rules each round.

Why we can do better

Problem: Re-sorting an array of n elements after each smash costs O(n log n) per round, and there are up to n−1 rounds. A max-heap gives O(log n) per extraction and insertion — overall O(n log n).

Java — Sort each round

 import java.util.*;
class Solution {
public int lastStoneWeight(int[] stones) {
List<Integer> list = new ArrayList<>();
for (int s : stones) list.add(s);
while (list.size() > 1) {
Collections.sort(list);
int a = list.remove(list.size() - 1);
int b = list.remove(list.size() - 1);
if (a != b) list.add(a - b);
        }
return list.isEmpty() ? 0 : list.get(0);
    }
}

Python — Sort each round

 class Solution:
def lastStoneWeight(self, stones: list[int]) -> int:
while len(stones) > 1:
            stones.sort()
            a, b = stones.pop(), stones.pop()
if a != b:
                stones.append(a - b)
return stones[0] if stones else 0 

Metric	Value
Time	O(n² log n) — sort O(n log n) per round × n rounds
Space	O(n)

Section Three · Approach 2

Max-Heap — O(n log n)

A max-heap always gives you the largest element in O(1) and extracts it in O(log n). Each round: pop the two largest, smash them, and push back the remainder if any. Repeat until ≤ 1 stone.

💡 Mental model: Imagine a sumo tournament bracket. The two heaviest wrestlers always face each other in the final. The winner (difference in weight) drops down to fight in the next round. A max-heap is your tournament bracket — the champion (heaviest) always floats to the top, and extracting the finalists costs O(log n) to re-arrange.

Algorithm

Step 1: Insert all stones into a max-heap.
Step 2: While heap has ≥ 2 elements: poll the two largest.
Step 3: If they differ, push first - second back.
Step 4: Return heap.peek() if one element remains, else 0.

🎯 When to recognize this pattern:

Any simulation that repeatedly needs the maximum (or minimum) element from a dynamic collection — think heap.
The signal is "pick the best available, modify, put it back." This pattern appears in LC 1046 (Last Stone Weight), LC 621 (Task Scheduler), LC 767 (Reorganize String), and merge-k-sorted problems.

Java max-heap trick:

Java's PriorityQueue is a min-heap by default.
For a max-heap, use new PriorityQueue<>(Collections.reverseOrder()).
In Python, negate values: push -stone and pop gives the most-negative (i.e., largest original).

Section Four · Trace

Visual Walkthrough

Trace through stones = [2, 7, 4, 1, 8, 1]:

Max-Heap simulation — smash two heaviest each round

Section Five · Implementation

Code — Java & Python

Java — Max-Heap (PriorityQueue reversed)

 import java.util.*;
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> heap =
new PriorityQueue<>(Collections.reverseOrder()); // max-heap for (int s : stones) heap.offer(s);
while (heap.size() > 1) {
int first  = heap.poll(); // heaviest int second = heap.poll(); // second heaviest if (first != second)
                heap.offer(first - second); // remainder survives
}
return heap.isEmpty() ? 0 : heap.peek();
    }
}

Python — Max-Heap (negate values)

 import heapq
class Solution:
def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones] # negate for max-heap
heapq.heapify(heap)
while len(heap) > 1:
            first  = -heapq.heappop(heap) # largest (un-negate)
second = -heapq.heappop(heap)
if first != second:
                heapq.heappush(heap, -(first - second))
return -heap[0] if heap else 0 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort every round	O(n² log n)	O(n)	Simple but redundant re-sorting
Sorted insert (bisect)	O(n²)	O(n)	O(log n) find + O(n) shift per round
Max-Heap ← optimal	O(n log n)	O(n)	O(log n) per poll/offer × n rounds

Why not a sorted array?:

Inserting into a sorted array is O(n) due to shifting elements. A heap gives O(log n) per insertion and extraction.
For n=30 the difference is negligible, but the heap solution is the standard pattern for interviews.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single stone	`[5]`	No smashing needed → return 5.
Two equal stones	`[3, 3]`	Both destroyed → heap empty → return 0.
All same weight	`[2, 2, 2, 2]`	Pair-wise destruction → return 0 (even count) or one stone (odd).
Already sorted ascending	`[1, 2, 3]`	Heap reorders to [3, 2, 1]. Smash 3-2=1, then 1-1=0 → return 0.
Large difference	`[1000, 1]`	999 survives. One round, one stone remains.
All ones	`[1, 1, 1]`	Smash 1,1→0. One stone (1) remains.

⚠ Common Mistake (Python): Forgetting to negate when pushing the remainder back. After computing first - second, you must push -(first - second) to maintain the max-heap invariant. Pushing the positive difference treats it as a small number in the min-heap, corrupting the order.

← Back to Heap problems

LearningTree

LC 1046 · Last Stone Weight — Solution & Explanation | DSA Guide