Pseudo-code

text
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 error. The repeated sorting is redundant because the array is largely sorted except for the one new element we insert.

Core Insight for Last Stone Weight

The inefficiency of the brute force method lies in re-sorting the entire array after every "smash" operation. We only change one value (inserting the remainder), but we pay the cost of sorting everything.

The Max-Heap data structure is designed specifically for this scenario. It maintains a partial order where the root node is always the maximum element.

1. Access Max: We can access the heaviest stone in $O(1)$.
2. Extract Max: We can remove the heaviest stone in $O(\log N)$.
3. Insert: We can add the resulting stone (if any) back in $O(\log N)$.

By using a Max-Heap, we reduce the cost of the main loop operation from $O(N \log N)$ (sorting) to $O(\log N)$ (heapify).

Visual Description: Imagine the stones organized in a binary tree structure. The invariant enforced is that every parent node is heavier than or equal to its children. The root of this tree holds the heaviest stone. When we extract the root, the last node in the tree moves to the root position and "sifts down" to restore the order. We do this twice to get the two heaviest stones. If a new stone is produced (the difference), we insert it at the bottom and let it "bubble up" to its correct position based on weight.

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.

Reference Implementation

C++ Solution for LeetCode 1046

cpp
#include <vector>
#include <queue>

class Solution {
public:
    int lastStoneWeight(std::vector<int>& stones) {
        // Use a Max-Heap (priority_queue defaults to max-heap in C++)
        std::priority_queue<int> maxHeap(stones.begin(), stones.end());
        
        while (maxHeap.size() > 1) {
            // Extract the two heaviest stones
            int y = maxHeap.top();
            maxHeap.pop();
            
            int x = maxHeap.top();
            maxHeap.pop();
            
            // If they are not equal, push the difference back
            if (x != y) {
                maxHeap.push(y - x);
            }
        }
        
        // If heap is empty return 0, otherwise return the last stone
        return maxHeap.empty() ? 0 : maxHeap.top();
    }
};

Java Solution for LeetCode 1046

java
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Java's PriorityQueue is a Min-Heap by default.
        // Use Collections.reverseOrder() to make it a Max-Heap.
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int stone : stones) {
            maxHeap.add(stone);
        }
        
        while (maxHeap.size() > 1) {
            // Extract the two heaviest stones
            int y = maxHeap.poll();
            int x = maxHeap.poll();
            
            // If weights differ, add the remaining piece back
            if (y != x) {
                maxHeap.add(y - x);
            }
        }
        
        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

Python Solution for LeetCode 1046

python
import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        # Python's heapq is a Min-Heap. 
        # We negate values to simulate a Max-Heap.
        max_heap = [-s for s in stones]
        heapq.heapify(max_heap)
        
        while len(max_heap) > 1:
            # Pop the heaviest (most negative)
            y = -heapq.heappop(max_heap)
            # Pop the second heaviest
            x = -heapq.heappop(max_heap)
            
            if x != y:
                # Push the negative difference back
                heapq.heappush(max_heap, -(y - x))
        
        return -max_heap[0] if max_heap else 0