Last Stone Weight

LeetCode 1046: Last Stone Weight Solution & Explanation

Problem Overview

TL;DR: To solve this problem efficiently, use a Max-Heap to repeatedly extract and process the two heaviest stones until one or zero remain.

The problem asks us to simulate a game involving a collection of stones, each having a specific weight. In every round, we must select the two heaviest stones and smash them together. The outcome depends on their weights:

• If they are equal, both are destroyed.
• If they differ, the smaller one is destroyed, and the larger one remains with a reduced weight equal to the difference.

We continue this process until there is at most one stone left. We must return the weight of the remaining stone or 0 if none exist. This is a popular interview question that tests your ability to manage dynamic datasets where the maximum element is constantly required.

Brute Force Approach for Last Stone Weight

The naive approach attempts to simulate the process directly using a standard array or list. Since we always need the two heaviest stones, we can sort the array to find them.

Naive Algorithm

1. Sort the array of stones in ascending order.
2. While the array has more than 1 element:
   • Remove the last element (the heaviest, let's call it y).
   • Remove the new last element (the second heaviest, x).
   • If x != y, calculate new_weight = y - x and insert it back into the array.
   • Re-sort the array to ensure the next iteration picks the correct maximums.
3. If the array is empty, return 0; otherwise, return the single element.

Pseudo-code

function lastStoneWeight(stones):
    while stones.length > 1:
        stones.sort()
        y = stones.pop()
        x = stones.pop()
        if x != y:
            stones.append(y - x)
    
    return stones[0] if stones.length == 1 else 0

Complexity Analysis

• Time Complexity: Inside the while loop, which runs approximately $N$ times (where $N$ is the number of stones), we perform a sort operation. Sorting takes $O(N \log N)$. Therefore, the total time complexity is $O(N^2 \log N)$.
• Why it fails: While the constraints for LeetCode 1046 are small ($N \le 30$), allowing this solution to pass, this approach is fundamentally inefficient. In a standard interview setting with constraints up to $N = 10^5$, an $O(N^2 \log N)$ algorithm would result in a Time Limit Exceeded (TLE) error. The repeated sorting is redundant because the array is largely sorted except for the one new element we insert.

Algorithm Strategy: Heap (Priority Queue) Patterns

1. Initialization: Transform the input array stones into a Max-Heap. This ensures the heaviest stone is immediately accessible.
   • Note: Some languages (like Python) only provide a Min-Heap by default. In such cases, we simulate a Max-Heap by negating all weight values (e.g., store 8 as -8). The "smallest" number (-8) corresponds to the largest original weight.
2. Simulation Loop: Continue the process as long as the heap contains more than one element.
   • Extract: Pop the top element from the heap. This is y (the heaviest).
   • Extract: Pop the new top element. This is x (the second heaviest).
   • Compare and Insert: Calculate the difference y - x. If the result is greater than 0, push this new weight back into the heap. The heap automatically rebalances.
3. Termination: Once the loop finishes, check the heap size.
   • If the heap is empty, return 0.
   • If one element remains, return that element.

Execution Flow

Let's trace the algorithm with stones = [2, 7, 4, 1, 8, 1].

1. Build Heap: The array is converted to a Max-Heap. Conceptually, the available weights are {8, 7, 4, 2, 1, 1}.
2. Iteration 1:
   • Pop Max: 8 (Heaviest).
   • Pop Max: 7 (Second heaviest).
   • Smash: 8 - 7 = 1.
   • Push 1 back into heap.
   • Heap state (weights): {4, 2, 1, 1, 1}.
3. Iteration 2:
   • Pop Max: 4.
   • Pop Max: 2.
   • Smash: 4 - 2 = 2.
   • Push 2 back into heap.
   • Heap state (weights): {2, 1, 1, 1}.
4. Iteration 3:
   • Pop Max: 2.
   • Pop Max: 1.
   • Smash: 2 - 1 = 1.
   • Push 1 back into heap.
   • Heap state (weights): {1, 1, 1}.
5. Iteration 4:
   • Pop Max: 1.
   • Pop Max: 1.
   • Smash: 1 - 1 = 0.
   • Push nothing (since result is 0).
   • Heap state (weights): {1}.
6. Termination: Loop ends because heap size is 1. Return 1.

Proof of Correctness

The correctness relies on the Max-Heap invariant. At any step k, the algorithm requires the two largest elements $S_1$ and $S_2$ from the current set $S$. The Max-Heap guarantees that the first pop() returns $\max(S)$ and the second pop() returns $\max(S \setminus \{S_1\})$.

The logic strictly follows the problem statement:

• If $S_1 == S_2$, both are removed (set size decreases by 2).
• If $S_1 \neq S_2$, $S_1 - S_2$ is added (set size decreases by 1).

Since the number of stones strictly decreases in every iteration, the loop is guaranteed to terminate. When it terminates, the remaining state represents the result of the simulation.

Pattern Reuse Notes

The Heap - Top K Elements pattern is versatile. Understanding how to maintain access to the "best" or "largest" elements dynamically is key to solving several other problems:

• LeetCode 215: Kth Largest Element in an Array - Instead of smashing stones, you simply extract the Max $K$ times (or maintain a Min-Heap of size $K$).
• LeetCode 347: Top K Frequent Elements - Here, the "weight" is the frequency of the number. The heap organizes elements by frequency count.
• LeetCode 451: Sort Characters By Frequency - Similar to Top K Frequent, but you reconstruct a string based on the priority queue extraction.
• LeetCode 506: Relative Ranks - Uses a heap to assign ranks (Gold, Silver, Bronze) based on score magnitude.

Reference Implementation

C++ Solution for LeetCode 1046

1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    int lastStoneWeight(std::vector<int>& stones) {
7        // Use a Max-Heap (priority_queue defaults to max-heap in C++)
8        std::priority_queue<int> maxHeap(stones.begin(), stones.end());
9        
10        while (maxHeap.size() > 1) {
11            // Extract the two heaviest stones
12            int y = maxHeap.top();
13            maxHeap.pop();
14            
15            int x = maxHeap.top();
16            maxHeap.pop();
17            
18            // If they are not equal, push the difference back
19            if (x != y) {
20                maxHeap.push(y - x);
21            }
22        }
23        
24        // If heap is empty return 0, otherwise return the last stone
25        return maxHeap.empty() ? 0 : maxHeap.top();
26    }
27};

Java Solution for LeetCode 1046

1import java.util.PriorityQueue;
2import java.util.Collections;
3
4class Solution {
5    public int lastStoneWeight(int[] stones) {
6        // Java's PriorityQueue is a Min-Heap by default.
7        // Use Collections.reverseOrder() to make it a Max-Heap.
8        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
9        
10        for (int stone : stones) {
11            maxHeap.add(stone);
12        }
13        
14        while (maxHeap.size() > 1) {
15            // Extract the two heaviest stones
16            int y = maxHeap.poll();
17            int x = maxHeap.poll();
18            
19            // If weights differ, add the remaining piece back
20            if (y != x) {
21                maxHeap.add(y - x);
22            }
23        }
24        
25        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
26    }
27}

Python Solution for LeetCode 1046

1import heapq
2
3class Solution:
4    def lastStoneWeight(self, stones: list[int]) -> int:
5        # Python's heapq is a Min-Heap. 
6        # We negate values to simulate a Max-Heap.
7        max_heap = [-s for s in stones]
8        heapq.heapify(max_heap)
9        
10        while len(max_heap) > 1:
11            # Pop the heaviest (most negative)
12            y = -heapq.heappop(max_heap)
13            # Pop the second heaviest
14            x = -heapq.heappop(max_heap)
15            
16            if x != y:
17                # Push the negative difference back
18                heapq.heappush(max_heap, -(y - x))
19        
20        return -max_heap[0] if max_heap else 0