276. Last Stone Weight
🔗 LeetCode Problem: 1046. Last Stone Weight
📊 Difficulty: Easy
🏷️ Topics: Array, Heap (Priority Queue)
Problem Statement
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.
Example 2:
Input: stones = [1]
Output: 1
Constraints:
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
🌟 The Natural Thinking Process
When you first see this problem:
Question: How do I find the two heaviest stones?
First Thought: "I can sort the array!"
- Sort → largest at end
- Take last two
- Calculate difference
- Put back and repeat
Is this optimal? Probably not, but it WORKS!
Let's code this first, then optimize.
The Evolution:
BRUTE FORCE THINKING:
"Need two largest → Sort entire array every time"
Time: O(n² log n) - sort n times
⬇
REALIZATION:
"Wait, I'm sorting ENTIRE array just to get max?"
"I only care about maximum, not full order!"
⬇
OPTIMIZATION:
"What if I use a data structure that MAINTAINS max?"
"MAX-HEAP! Get max in O(log n), not O(n log n)!"
Time: O(n log n) - much better!
🎯 Approach 1: Brute Force - Sort Every Time ⭐
The First Natural Solution
The Thought Process:
Step 1: Read problem
"Need to repeatedly find two largest stones"
Step 2: How to find largest?
"Sort the array! Largest will be at end"
Step 3: What about next time?
"Array changes... sort again!"
Step 4: When to stop?
"When 0 or 1 stone left"
This is not optimal, but let's implement it!
Visual Tracking - Complete Dry Run
stones = [2, 7, 4, 1, 8, 1]
═══════════════════════════════════════════════════════════════
ROUND 1
═══════════════════════════════════════════════════════════════
Current stones: [2, 7, 4, 1, 8, 1]
Step 1: Sort array
Sorted: [1, 1, 2, 4, 7, 8]
↑ ↑ ↑
smallest 2nd largest
largest
Step 2: Remove two largest
stone1 = 8 (remove from end)
stones: [1, 1, 2, 4, 7]
stone2 = 7 (remove from end)
stones: [1, 1, 2, 4]
Step 3: Calculate difference
8 - 7 = 1
Step 4: Is difference 0?
No → Add back 1
stones: [1, 1, 2, 4, 1]
State after Round 1:
stones = [1, 1, 2, 4, 1] (5 stones)
Continue? YES (more than 1 stone)
═══════════════════════════════════════════════════════════════
ROUND 2
═══════════════════════════════════════════════════════════════
Current stones: [1, 1, 2, 4, 1]
Step 1: Sort array
Sorted: [1, 1, 1, 2, 4]
↑ ↑
2nd largest
largest
Step 2: Remove two largest
stone1 = 4
stones: [1, 1, 1, 2]
stone2 = 2
stones: [1, 1, 1]
Step 3: Calculate difference
4 - 2 = 2
Step 4: Add back
stones: [1, 1, 1, 2]
State after Round 2:
stones = [1, 1, 1, 2] (4 stones)
Continue? YES
═══════════════════════════════════════════════════════════════
ROUND 3
═══════════════════════════════════════════════════════════════
Current stones: [1, 1, 1, 2]
Step 1: Sort array
Sorted: [1, 1, 1, 2]
↑ ↑
2nd largest
largest
Step 2: Remove two largest
stone1 = 2
stones: [1, 1, 1]
stone2 = 1
stones: [1, 1]
Step 3: Calculate difference
2 - 1 = 1
Step 4: Add back
stones: [1, 1, 1]
State after Round 3:
stones = [1, 1, 1] (3 stones)
Continue? YES
═══════════════════════════════════════════════════════════════
ROUND 4
═══════════════════════════════════════════════════════════════
Current stones: [1, 1, 1]
Step 1: Sort array
Sorted: [1, 1, 1]
↑ ↑
2nd largest
largest
Step 2: Remove two largest
stone1 = 1
stones: [1, 1]
stone2 = 1
stones: [1]
Step 3: Calculate difference
1 - 1 = 0
Step 4: Is difference 0?
YES → Both destroyed, don't add back
stones: [1]
State after Round 4:
stones = [1] (1 stone)
Continue? NO (only 1 stone left)
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Final stones: [1]
Answer: 1 ✓
Summary:
Start: [2, 7, 4, 1, 8, 1] (6 stones)
Round 1: Sort → [1,1,2,4,7,8] → Remove 8,7 → Add 1 → [1,1,2,4,1]
Round 2: Sort → [1,1,1,2,4] → Remove 4,2 → Add 2 → [1,1,1,2]
Round 3: Sort → [1,1,1,2] → Remove 2,1 → Add 1 → [1,1,1]
Round 4: Sort → [1,1,1] → Remove 1,1 → Add 0 → [1]
End: [1]
Implementation
import java.util.*;
/**
* Brute Force: Sort every round
* Time: O(n² log n) - Sort n times
* Space: O(n) - ArrayList storage
*/
class Solution {
public int lastStoneWeight(int[] stones) {
// Convert to list for easy manipulation
List<Integer> stoneList = new ArrayList<>();
for (int stone : stones) {
stoneList.add(stone);
}
// Keep smashing until ≤ 1 stone
while (stoneList.size() > 1) {
// Sort to get largest at end
Collections.sort(stoneList);
// Remove two largest (from end)
int stone1 = stoneList.remove(stoneList.size() - 1);
int stone2 = stoneList.remove(stoneList.size() - 1);
// Add back difference if not equal
if (stone1 != stone2) {
stoneList.add(stone1 - stone2);
}
}
return stoneList.isEmpty() ? 0 : stoneList.get(0);
}
}
⏰ Time: O(n² log n) - n rounds, each sorts O(n log n)
💾 Space: O(n) - List storage
Why This Works:
✓ Correctly finds two largest each round
✓ Handles all edge cases
✓ Simple to understand and code
But... sorting entire array every time is WASTEFUL!
💡 The AHA Moment - Why Brute Force is Slow
PROBLEM ANALYSIS:
Round 1: Sort 6 elements → O(6 log 6) ≈ 15 operations
Round 2: Sort 5 elements → O(5 log 5) ≈ 12 operations
Round 3: Sort 4 elements → O(4 log 4) ≈ 8 operations
Round 4: Sort 3 elements → O(3 log 3) ≈ 5 operations
Total: ~40 operations just for sorting!
THE KEY INSIGHT:
"I'm sorting ENTIRE array just to find maximum!"
What if array is: [1, 1, 1, 1, 1, 100]
After sorting: [1, 1, 1, 1, 1, 100]
I sorted 5 small stones unnecessarily!
I only cared about the 100!
REALIZATION:
"I don't need FULL order, just MAXIMUM!"
"What data structure gives me maximum efficiently?"
MAX-HEAP! ✨
🎯 Approach 2: Optimized - Max-Heap ⭐⭐⭐
The Optimized Solution
The Evolution of Thought:
Brute Force: Sort entire array every time
⬇
Question: "Do I need full sort just for maximum?"
⬇
Answer: "NO! I only need maximum!"
⬇
Better Idea: "Use MAX-HEAP!"
- Get maximum: O(log n) not O(n log n)
- Add element: O(log n)
- Perfect for this problem!
Understanding Max-Heap
WHAT IS MAX-HEAP?
A tree structure where parent > children
Always maintains largest element at ROOT (top)
Example: [2, 7, 4, 1, 8, 1]
Max-Heap Structure:
8
/ \
7 4
/ \ /
1 2 1
Operations:
- peek(): Get maximum (top) → O(1)
- poll(): Remove maximum → O(log n)
- offer(): Add element → O(log n)
Why better than sorting?
- Don't sort entire array
- Only maintain partial order
- Much faster!
Visual Tracking - Complete Dry Run with Heap
stones = [2, 7, 4, 1, 8, 1]
═══════════════════════════════════════════════════════════════
INITIALIZATION: Build Max-Heap
═══════════════════════════════════════════════════════════════
Add stones one by one to max-heap:
Add 2:
Heap: [2]
Add 7:
Heap: [7, 2]
↑
largest
Add 4:
Heap: [7, 2, 4]
↑
largest
Add 1:
Heap: [7, 2, 4, 1]
↑
largest
Add 8:
Heap: [8, 7, 4, 1, 2]
↑
NEW largest!
Add 1:
Heap: [8, 7, 4, 1, 2, 1]
↑
largest
Heap visualization:
8
/ \
7 4
/ \ /
1 2 1
Heap size: 6
Ready to start smashing!
═══════════════════════════════════════════════════════════════
ROUND 1: Smash Two Heaviest
═══════════════════════════════════════════════════════════════
Current heap: [8, 7, 4, 1, 2, 1]
Step 1: Remove largest (poll)
stone1 = heap.poll() = 8
Heap after removal: [7, 2, 4, 1, 1]
7
/ \
2 4
/ \
1 1
Step 2: Remove next largest (poll)
stone2 = heap.poll() = 7
Heap after removal: [4, 2, 1, 1]
4
/ \
2 1
/
1
Step 3: Calculate difference
stone1 = 8, stone2 = 7
8 - 7 = 1
┌─────────────────────────────────────────┐
│ Smash: 8 and 7 │
│ Result: 1 │
│ Action: Add back to heap │
└─────────────────────────────────────────┘
Step 4: Add difference back (offer)
heap.offer(1)
Heap: [4, 2, 1, 1, 1]
4
/ \
2 1
/ \
1 1
Heap size: 5
Continue? YES
═══════════════════════════════════════════════════════════════
ROUND 2: Smash Two Heaviest
═══════════════════════════════════════════════════════════════
Current heap: [4, 2, 1, 1, 1]
Step 1: Remove largest
stone1 = heap.poll() = 4
Heap: [2, 1, 1, 1]
2
/ \
1 1
/
1
Step 2: Remove next largest
stone2 = heap.poll() = 2
Heap: [1, 1, 1]
1
/ \
1 1
Step 3: Calculate difference
4 - 2 = 2
┌─────────────────────────────────────────┐
│ Smash: 4 and 2 │
│ Result: 2 │
│ Action: Add back to heap │
└─────────────────────────────────────────┘
Step 4: Add back
heap.offer(2)
Heap: [2, 1, 1, 1]
2
/ \
1 1
/
1
Heap size: 4
Continue? YES
═══════════════════════════════════════════════════════════════
ROUND 3: Smash Two Heaviest
═══════════════════════════════════════════════════════════════
Current heap: [2, 1, 1, 1]
Step 1: Remove largest
stone1 = heap.poll() = 2
Heap: [1, 1, 1]
Step 2: Remove next largest
stone2 = heap.poll() = 1
Heap: [1, 1]
Step 3: Calculate difference
2 - 1 = 1
┌─────────────────────────────────────────┐
│ Smash: 2 and 1 │
│ Result: 1 │
│ Action: Add back to heap │
└─────────────────────────────────────────┘
Step 4: Add back
heap.offer(1)
Heap: [1, 1, 1]
Heap size: 3
Continue? YES
═══════════════════════════════════════════════════════════════
ROUND 4: Smash Two Heaviest
═══════════════════════════════════════════════════════════════
Current heap: [1, 1, 1]
Step 1: Remove largest
stone1 = heap.poll() = 1
Heap: [1, 1]
Step 2: Remove next largest
stone2 = heap.poll() = 1
Heap: [1]
Step 3: Calculate difference
1 - 1 = 0
┌─────────────────────────────────────────┐
│ Smash: 1 and 1 │
│ Same weight! │
│ Action: Both destroyed, nothing added │
└─────────────────────────────────────────┘
Step 4: Both destroyed
Don't add anything
Heap: [1]
Heap size: 1
Continue? NO (only 1 stone)
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Final heap: [1]
Answer: 1 ✓
Key Observations:
- Never sorted entire array!
- Each poll/offer: O(log n)
- Much faster than sorting
Implementation
import java.util.*;
/**
* Optimized: Max-Heap approach
* Time: O(n log n)
* Space: O(n)
*/
class Solution {
public int lastStoneWeight(int[] stones) {
// Max-heap (reverse natural order for max on top)
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());
// Add all stones to heap: O(n log n)
for (int stone : stones) {
maxHeap.offer(stone);
}
// Smash stones until ≤ 1 remains
while (maxHeap.size() > 1) {
// Remove two largest: O(log n) each
int stone1 = maxHeap.poll();
int stone2 = maxHeap.poll();
// Add back difference if not equal: O(log n)
if (stone1 != stone2) {
maxHeap.offer(stone1 - stone2);
}
}
// Return last stone or 0 if empty
return maxHeap.isEmpty() ? 0 : maxHeap.peek();
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.lastStoneWeight(new int[]{2,7,4,1,8,1})); // 1
System.out.println(sol.lastStoneWeight(new int[]{1})); // 1
System.out.println(sol.lastStoneWeight(new int[]{5,5})); // 0
}
}
⏰ Time: O(n log n) - Build heap + n rounds of O(log n)
💾 Space: O(n) - Heap storage
📊 Approach Comparison - The Growth Journey
┌──────────────┬─────────────┬──────────┬──────────────────────┐
│ Approach │ Time │ Space │ Key Insight │
├──────────────┼─────────────┼──────────┼──────────────────────┤
│ Sorting │ O(n² log n) │ O(n) │ First natural idea │
│ Max-Heap │ O(n log n) │ O(n) │ Don't need full sort │
└──────────────┴─────────────┴──────────┴──────────────────────┘
THE LEARNING PROGRESSION:
Level 1: Brute Force (Sorting)
Thought: "I need max → Sort everything!"
Works? YES ✓
Optimal? NO ✗
Learning: Got solution, but can improve
Level 2: Optimization Insight
Question: "Do I need FULL sort for just MAX?"
Realization: "Only care about maximum!"
Idea: "Use data structure that tracks max!"
Level 3: Max-Heap Solution
Implementation: Use PriorityQueue with reverseOrder
Result: O(n log n) instead of O(n² log n)
Growth: Learned when heap is better than sorting!
CONCRETE EXAMPLE (n=30):
Sorting Approach:
Round 1: Sort 30 elements → ~150 ops
Round 2: Sort 29 elements → ~145 ops
...
Round 30: Sort 1 element → ~1 op
Total: ~4,500 operations! 😱
Max-Heap Approach:
Build heap: 30 insertions → ~150 ops
Round 1: 2 polls + 1 offer → ~15 ops
Round 2: 2 polls + 1 offer → ~15 ops
...
Total: ~600 operations! 🚀
7.5x FASTER! ✨
💡 Key Learnings - Your Growth
WHAT YOU LEARNED:
1. BRUTE FORCE FIRST:
✓ Natural thinking: "Sort to get max"
✓ Valid solution, just not optimal
✓ Important to code what works first!
2. IDENTIFY BOTTLENECK:
✓ Sorting entire array is wasteful
✓ Only need maximum, not full order
✓ This insight leads to optimization!
3. DATA STRUCTURE CHOICE:
✓ Max-heap perfect for "repeated max queries"
✓ O(log n) per operation vs O(n log n) sort
✓ Learned WHEN to use heap over sorting
4. COMPLEXITY IMPROVEMENT:
✓ O(n² log n) → O(n log n)
✓ Significant practical speedup
✓ Same space complexity O(n)
INTERVIEW STRATEGY:
If You Think of Sorting First:
"I can solve this by sorting each round for O(n² log n).
But that's wasteful - I'm sorting just to get max.
Better approach is max-heap for O(n log n).
Let me implement the heap solution."
✓ Shows problem-solving progression
✓ Demonstrates optimization thinking
✓ Impresses interviewer with trade-off analysis
This is EXACTLY how you grow! 🌱→🌳
⚠️ Common Mistakes
Mistake 1: Using min-heap instead of max-heap
// ❌ WRONG - Gives smallest stones
PriorityQueue<Integer> heap = new PriorityQueue<>();
// ✓ CORRECT - Gives largest stones
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());
Mistake 2: Adding back when equal
// ❌ WRONG - Adds 0 unnecessarily
int diff = stone1 - stone2;
heap.offer(diff);
// ✓ CORRECT - Only add if different
if (stone1 != stone2) {
heap.offer(stone1 - stone2);
}
Mistake 3: Wrong loop condition
// ❌ WRONG - Can't smash if only 1 stone
while (!heap.isEmpty()) {
// What if heap has 1 stone? Can't remove 2!
}
// ✓ CORRECT - Need at least 2 stones
while (heap.size() > 1) {
// Always have 2+ stones to smash
}
Mistake 4: Not handling empty heap
// ❌ WRONG - Exception if empty
return heap.peek();
// ✓ CORRECT - Return 0 if no stones
return heap.isEmpty() ? 0 : heap.peek();
🎯 Pattern Recognition
Problem Type: Repeated Maximum Selection
Core Pattern: Max-Heap for Priority Processing
When to Apply:
✓ Repeatedly need largest/smallest element
✓ Process elements by priority
✓ Don't need full sort, just extremes
✓ Dynamic updates (add/remove)
Recognition Keywords:
- "heaviest"/"largest"/"smallest"
- "repeatedly"/"at each turn"
- "pick two largest"
Similar Problems:
- Kth Largest Element (LC 215)
- Top K Frequent Elements (LC 347)
- Merge K Sorted Lists (LC 23)
- Find Median from Data Stream (LC 295)
📝 Quick Revision Notes
🎯 Core Concept:
Repeatedly smash two heaviest stones. Brute force: Sort every round O(n² log n). Optimized: Use max-heap O(n log n) - maintains max without full sort. Poll twice for largest, add back difference if not equal. Loop while size > 1. Return last stone or 0.
⚡ Quick Implementations:
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
public int lastStoneWeight(int[] a) {
// return naive(a);
return maxHeap(a);
}
private int maxHeap(int[] a) {
// step 1: create max heap which will always return max
// element present when polled.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
// step 2: put all elements in heap
for (int num : a) {
pq.offer(num);
}
// step 6: loop till only one element left
while (pq.size() > 1) {
// step 3: poll 2 elements which are greater than the rest of the elements.
int first = pq.poll();
int second = pq.poll();
int diff = first - second;
if (diff == 0) {
// step 4: if they are of equal strength, no need to add back to list
continue;
} else {
// step 5: add diff and continue the process
pq.offer(diff);
}
}
// step 7: return the left-out element
// why check size? for edge case (2,2), nothing will be left out
return pq.size() > 0 ? pq.poll() : 0;
}
private int naive(int[] a) {
// step 1: convert array to list for easy processing
ArrayList<Integer> list = new ArrayList<>();
for (int num : a) {
list.add(num);
}
// step 2: sort the list
Collections.sort(list);
// step 6: loop till only one element left
while (list.size() > 1) {
// step 3: remove last 2 elements which are greater
// than the rest of the elements.
int first = list.remove(list.size() - 1);
int second = list.remove(list.size() - 1);
int diff = first - second;
if (diff == 0) {
// step 4: if they are of equal strength, no need to add back to list
continue;
} else {
// step 5: add diff and sort the list and continue the process
list.add(diff);
Collections.sort(list);
}
}
// step 7: return the left-out element
// why check size? for edge case (2,2), nothing will be left out
return list.size() > 0 ? list.get(0) : 0;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lastStoneWeight(new int[] { 2, 7, 4, 1, 8, 1 }) == 1);
System.out.println(s.lastStoneWeight(new int[] { 1 }) == 1);
System.out.println(s.lastStoneWeight(new int[] { 2, 2 }) == 0);
}
}
🔑 Key Insights:
- Natural Progression: Sort → Realize waste → Use heap
- Bottleneck: Sorting entire array just for max
- Optimization: Heap maintains max in O(log n)
- Max-Heap:
Collections.reverseOrder() - Loop:
while (size > 1)- need 2 to smash - Conditional: Only add if
s1 != s2 - Growth: From O(n² log n) to O(n log n)! ✓
🎪 Memory Aid:
"Sort works but wastes time!"
"Heap tracks max efficiently!"
"This is how you grow - brute force → optimize!" ✨
🧪 Edge Cases
Case 1: Single stone
Input: [1]
Output: 1
No smashing needed
Case 2: Two equal stones
Input: [5, 5]
Output: 0
Both destroyed
Case 3: All different
Input: [1, 2, 3, 4]
Various combinations
All handled correctly! ✓
🎓 Complexity Analysis
Approach 1: Sorting
Time: O(n² log n)
Each round: O(n log n) to sort
n rounds: n × (n log n) = O(n² log n)
Space: O(n)
ArrayList storage
Approach 2: Max-Heap
Time: O(n log n)
Build heap: n insertions × O(log n) = O(n log n)
Each round: 2 polls + 1 offer = O(log n)
n rounds: n × O(log n) = O(n log n)
Total: O(n log n) + O(n log n) = O(n log n)
Space: O(n)
Heap storage
Happy practicing! 🎯
Note: This problem is PERFECT for learning heap optimization! You naturally think "sort to get max" first - that works! But then you realize "I'm sorting just for max" and discover heaps are better. This progression from brute force → optimized is EXACTLY how you grow as a problem solver! The journey from O(n² log n) to O(n log n) teaches you when heaps beat sorting. Never skip the brute force - it builds intuition! 💪✨🌱