LeetCode 1046 - Last Stone Weight

This problem asks us to repeatedly simulate a process involving stones with different weights. At every turn, we must select the two heaviest stones, smash them together, and update the collection based on the result.

leetcodeeasyarrayheap-(priority-queue)

LeetCode Problem 1046

Difficulty: 🟢 Easy
Topics: Array, Heap (Priority Queue)

Solution

Problem Understanding

This problem asks us to repeatedly simulate a process involving stones with different weights. At every turn, we must select the two heaviest stones, smash them together, and update the collection based on the result.

If the two heaviest stones have the same weight, both are destroyed and disappear from the collection. If the stones have different weights, the smaller stone is destroyed, and the larger stone survives with a reduced weight equal to the difference between the two.

We continue this process until there is either one stone left or no stones remaining. The goal is to return the weight of the final stone, or 0 if every stone gets destroyed.

The input is an integer array stones, where each value represents the weight of one stone. The output is a single integer representing the last remaining stone's weight.

The constraints are small:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

These constraints tell us that the number of stones is very limited. Even an inefficient solution may pass, but the problem is designed to introduce an important data structure pattern, using a heap (priority queue) to efficiently retrieve the largest elements repeatedly.

An important observation is that the game always depends on the current two heaviest stones, meaning the collection changes dynamically after every operation. A naive implementation that repeatedly sorts or scans the array can work because the input size is small, but a priority queue is a cleaner and more scalable approach.

Several edge cases are worth identifying early. If there is only one stone, that stone is already the answer. If all stones cancel each other out perfectly, the result should be 0. Repeated duplicate values can also create chains of eliminations, so the implementation must carefully update the data structure after every smash.

Approaches

Brute Force Approach

The most straightforward way to solve this problem is to repeatedly sort the array.

At each iteration, we sort the stones in descending order so that the two heaviest stones appear at the front. We remove those two stones and compare their weights.

If the weights are equal, both disappear. If they differ, we insert the difference back into the list. We then repeat this process until at most one stone remains.

This approach is correct because sorting guarantees we always pick the two heaviest stones, exactly matching the rules of the problem. However, sorting the array after every smash is inefficient because sorting costs O(n log n) time, and we may repeat this operation many times.

Although the constraints are small enough for this solution to pass, it is not ideal from an algorithmic perspective.

Key Insight for an Optimal Solution

The important observation is that we repeatedly need access to the largest elements.

Instead of sorting the entire array after every operation, we can use a max heap, which allows us to efficiently retrieve and remove the largest element in O(log n) time.

A heap is well suited here because:

  1. We repeatedly need the largest values.
  2. The collection changes dynamically after every smash.
  3. We only need local ordering, not full sorting.

Python provides a built-in min heap, so we simulate a max heap by storing negative values. In Go, we implement a heap using the container/heap package and customize it to behave as a max heap.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² log n) O(1) or O(n) Repeatedly sorts the array after each smash
Optimal O(n log n) O(n) Uses a max heap for efficient largest-element retrieval

Algorithm Walkthrough

  1. Initialize a max heap with all stone weights. Since Python only supports a min heap, store each value as a negative number so the largest weight behaves like the smallest heap value.
  2. Convert the input list into a heap. This preprocessing step takes linear time and prepares the data structure for efficient removals.
  3. While the heap contains at least two stones, remove the two heaviest stones. These represent the required smash operation according to the problem rules.
  4. Compare the two stones. If they are equal, both are destroyed, so nothing gets inserted back into the heap.
  5. If the stones have different weights, compute the difference between them and insert the remaining stone back into the heap.
  6. Continue this process until the heap has at most one stone remaining.
  7. If one stone remains, return its weight. Otherwise, return 0.

Why it works

The correctness of the algorithm comes from maintaining the invariant that the heap always contains the current set of remaining stones. At every iteration, extracting the two maximum values guarantees we follow the exact game rule of smashing the two heaviest stones. Re-inserting the difference correctly models the surviving stone when the weights are unequal. Since each step faithfully simulates one legal move of the game, the final remaining value must be the correct answer.

Python Solution

from typing import List
import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Convert to max heap using negative values
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            heaviest = -heapq.heappop(max_heap)
            second_heaviest = -heapq.heappop(max_heap)

            if heaviest != second_heaviest:
                remaining_stone = heaviest - second_heaviest
                heapq.heappush(max_heap, -remaining_stone)

        return -max_heap[0] if max_heap else 0

The implementation begins by converting every stone weight into a negative value. This is necessary because Python's heapq module implements a min heap, while we need max heap behavior.

After calling heapify, the list becomes a valid heap structure in linear time.

Inside the loop, we repeatedly remove the two largest stones by popping the two smallest negative values. We convert them back into positive integers for comparison.

If the stones are unequal, we compute the difference and push the surviving stone back into the heap. Equal stones naturally disappear because nothing is added back.

Finally, when the loop ends, we either return the remaining stone or 0 if no stones remain.

Go Solution

package main

import (
	"container/heap"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func lastStoneWeight(stones []int) int {
	maxHeap := MaxHeap(stones)
	heap.Init(&maxHeap)

	for maxHeap.Len() > 1 {
		heaviest := heap.Pop(&maxHeap).(int)
		secondHeaviest := heap.Pop(&maxHeap).(int)

		if heaviest != secondHeaviest {
			heap.Push(&maxHeap, heaviest-secondHeaviest)
		}
	}

	if maxHeap.Len() == 0 {
		return 0
	}

	return heap.Pop(&maxHeap).(int)
}

The Go implementation uses the container/heap package, which requires defining a custom heap type implementing the heap.Interface.

The key customization happens in the Less method. By reversing the comparison from < to >, the heap behaves as a max heap instead of the default min heap.

Unlike Python, Go does not require negating values because the heap ordering can be customized directly. Since the constraints are small and stone weights are bounded, integer overflow is not a concern.

Worked Examples

Example 1

Input:

stones = [2,7,4,1,8,1]

After heap initialization, the largest stone is always accessible.

Step Two Heaviest Stones Result Remaining Stones
Initial - - [2,7,4,1,8,1]
1 8, 7 1 [4,2,1,1,1]
2 4, 2 2 [2,1,1,1]
3 2, 1 1 [1,1,1]
4 1, 1 0 [1]

Only one stone remains, so the answer is:

1

Example 2

Input:

stones = [1]

Since there is only one stone, no smashing occurs.

Step Heap State Action
Initial [1] Single stone remains

The result is:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Building the heap takes O(n), and each smash operation performs heap operations costing O(log n)
Space O(n) The heap stores all stones

The heap is initialized once in linear time. In the worst case, we perform approximately n smash operations, and each iteration involves two removals and possibly one insertion, each costing O(log n). Therefore, the overall complexity becomes O(n log n).

Test Cases

from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        import heapq

        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)

        while len(max_heap) > 1:
            first = -heapq.heappop(max_heap)
            second = -heapq.heappop(max_heap)

            if first != second:
                heapq.heappush(max_heap, -(first - second))

        return -max_heap[0] if max_heap else 0

solution = Solution()

assert solution.lastStoneWeight([2, 7, 4, 1, 8, 1]) == 1  # Provided example
assert solution.lastStoneWeight([1]) == 1  # Single stone
assert solution.lastStoneWeight([2, 2]) == 0  # Equal stones destroy each other
assert solution.lastStoneWeight([10, 4]) == 6  # Unequal pair
assert solution.lastStoneWeight([5, 5, 5, 5]) == 0  # All stones cancel
assert solution.lastStoneWeight([9, 3, 2, 10]) == 0  # Multiple reductions
assert solution.lastStoneWeight([1000]) == 1000  # Maximum stone weight
assert solution.lastStoneWeight([1, 1, 2]) == 0  # Chain elimination
assert solution.lastStoneWeight([3, 7, 8]) == 2  # Unequal sequence
assert solution.lastStoneWeight([31, 26, 33, 21, 40]) == 9  # Larger case
Test Why
[2,7,4,1,8,1] Validates the provided example
[1] Confirms single-element handling
[2,2] Verifies equal stones disappear
[10,4] Tests unequal smash behavior
[5,5,5,5] Ensures repeated cancellation works
[9,3,2,10] Tests multiple sequential heap updates
[1000] Validates upper bound stone value
[1,1,2] Checks chain elimination behavior
[3,7,8] Tests nontrivial unequal smashing
[31,26,33,21,40] Covers a larger mixed scenario

Edge Cases

Single Stone Input

When the input contains only one stone, there are no smash operations to perform. A naive implementation might incorrectly attempt to remove two elements and cause an index error. This implementation handles the case naturally because the loop only runs when at least two stones exist. The remaining stone is returned directly.

All Stones Cancel Out

Inputs such as [2,2] or [5,5,5,5] result in complete elimination of all stones. A buggy implementation might assume one stone always survives and attempt to access an empty heap. This solution safely checks whether the heap is empty and returns 0 if no stones remain.

Unequal Final Smash

Cases like [10,4] or [8,7] leave one surviving stone after subtraction. A common mistake is forgetting to reinsert the remaining weight into the data structure. This implementation explicitly pushes the difference back into the heap whenever the two stones are unequal.

Repeated Duplicate Values

Inputs with many repeated weights, such as [1,1,2] or [5,5,5,5], can trigger long chains of eliminations. Incorrect implementations may mishandle duplicates or fail to preserve heap ordering after updates. Because the heap automatically restores ordering after every insertion, the algorithm continues selecting the correct two heaviest stones throughout execution.