Last Stone Weight
Mahabharata — The Final Combat — When the Heaviest Stones Clash Until One Remains
दो भारी पत्थर टकराते — बड़ा अंतर बचता। महा-ढेर में बार-बार — अंत में एक या शून्य॥
*Two heaviest stones clash — their difference remains. In the max-heap, repeat — until one or none.*
The Story
Stones smash against each other. Every turn: pick the two heaviest stones y and x (y>=x). If equal: both destroyed. If not: the lighter (x) is destroyed, the heavier becomes y-x. Repeat until ≤1 stone remains. Return the weight of the last stone (0 if none).
For `stones=[2,7,4,1,8,1]`: - Heaviest: 8,7 → new stone 1 → [2,4,1,1,1] - Heaviest: 4,2 → new stone 2 → [2,1,1,1] - Heaviest: 2,1 → new stone 1 → [1,1,1] - Heaviest: 1,1 → destroyed → [1] - One stone left: return 1 ✓
**Max-Heap:** Always access the two maximum elements: ```java PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); for (int s : stones) pq.offer(s); while (pq.size() > 1) { int y = pq.poll(); // Heaviest int x = pq.poll(); // Second heaviest if (y != x) pq.offer(y - x); // Remainder } return pq.isEmpty() ? 0 : pq.peek(); ```
This is a straightforward max-heap application — simulation of a process requiring repeated access to maximums.
**The 'Greedy + Heap' pattern:** Unlike the 'maintain k elements' pattern (hp-1 through hp-7), this pattern uses the heap as a priority queue for simulation — always getting the most extreme elements for a process.
Trace `[2,7,4,1,8,1]` step by step with max-heap: - Init: pq=[8,7,4,2,1,1] - Poll 8,7 → 1 → pq=[4,2,1,1,1] - Poll 4,2 → 2 → pq=[2,1,1,1] - Poll 2,1 → 1 → pq=[1,1,1] - Poll 1,1 → equal → no push → pq=[1] - Size=1 → return 1 ✓
The Sorted-List Simulation
Sort each iteration, pick two largest, simulate. O(n² log n).
public int lastStoneWeightBruteForce(int[] stones) {
List<Integer> list = new ArrayList<>();
for (int s : stones) list.add(s);
while (list.size() > 1) {
Collections.sort(list);
int y=list.remove(list.size()-1);
int x=list.remove(list.size()-1);
if (y!=x) list.add(y-x);
}
return list.isEmpty() ? 0 : list.get(0);
}The Max-Heap Simulation Wisdom
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) pq.offer(s);
while (pq.size() > 1) {
int y = pq.poll(); // Heaviest
int x = pq.poll(); // Second heaviest
if (y != x) pq.offer(y - x);
}
return pq.isEmpty() ? 0 : pq.peek();
}Step-by-Step Walkthrough
[2,7,4,1,8,1] step-by-step: [8,7,4,2,1,1]→[4,2,1,1,1]→[2,1,1,1]→[1,1,1]→[1] Return 1 ✅
Deep Insight
**Two heap sub-patterns:** 1. **k-selection heap** (hp-1 to hp-7): Maintain a size-k heap to find kth element or top-k elements 2. **Greedy + heap simulation** (hp-8, hp-10): Use heap to repeatedly access extremes during a simulation
**Why max-heap?** The problem always requires the two LARGEST stones. Max-heap gives O(log n) access to the maximum, vs O(n) for a linear scan.
**Edge cases:** - All stones equal → all annihilate → return 0 - Single stone → return that stone's weight - Empty (after all annihilations) → return 0
**Related problems:** Task Scheduler (LeetCode 621) uses a similar greedy simulation with a max-heap of task frequencies.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n² log n) | O(n) | Re-sort each round |
| Optimal | O(n log n) | O(n) | Init heap O(n log n), at most n iterations each O(log n) |
Pattern Recognition
✅ Repeated maximum extraction → max-heap simulation ✅ Poll two maximums, process, conditionally push back ✅ Terminate when ≤1 elements ✅ Return 0 for empty heap **LeetCode Trigger Phrases:** → "last stone weight" → Repeatedly combine/smash two largest elements → Greedy heap simulation pattern
Bhagavad Gita 2.27
जातस्य हि ध्रुवो मृत्युर्ध्रुवं जन्म मृतस्य च। तस्मादपरिहार्येऽर्थे न त्वं शोचितुमर्हसि॥
For the one who is born, death is certain; and for the one who dies, birth is certain. Therefore, you should not grieve over the inevitable.
Connection: Stones clash and are destroyed — smaller ones inevitably. The heaviest always prevails until it too finds an equal match and both are annihilated. This cycle of confrontation and dissolution mirrors the Gita's teaching on the inevitability of birth and death. The max-heap presides over this cosmic cycle, always presenting the two strongest forces for their inevitable clash, until at last one stone (or none) remains — the final weight of all the accumulated conflict.