-
Notifications
You must be signed in to change notification settings - Fork 0
095 — Last Stone Weight
LeetCode 1046 · Easy. Given an array stones of stone weights, repeatedly pick the two heaviest stones and smash them together: if they're equal, both are destroyed; otherwise the lighter one is destroyed and the heavier one's new weight becomes the difference. Return the weight of the last remaining stone, or 0 if none remain.
Picture a demolition derby where, every round, only the two heaviest-remaining cars get to crash into each other, and the loser is towed off (or, if it's an exact tie, both get towed). To run this derby correctly, all you ever need to know at any moment is: "which two are currently the heaviest?" You never care about the ordering of the cars way down at the bottom of the pack — they just sit and wait their turn, if they ever get one. That's the whole problem: repeatedly ask "who's #1 and #2 right now," combine them, and put the result back in the mix.
"Repeatedly combine the two largest/heaviest elements" is the tell. Any time an algorithm needs "the current maximum" over and over, with the collection changing after every step (an element removed, a new one possibly added back in), that's a max-heap — the exact shape of Last Stone Weight, Task Scheduler, and Huffman-coding-style problems.
Sort the stones descending, pop the two heaviest off the front, compute the result, and re-sort the whole array before the next round.
func lastStoneWeightBruteForce(_ stones: [Int]) -> Int {
var stones = stones.sorted(by: >)
while stones.count > 1 {
let first = stones.removeFirst()
let second = stones.removeFirst()
let diff = first - second
if diff > 0 {
stones.append(diff)
}
stones.sort(by: >)
}
return stones.first ?? 0
}
// smoke test
print(lastStoneWeightBruteForce([2, 7, 4, 1, 8, 1])) // 1
print(lastStoneWeightBruteForce([1])) // 1 — single stone, nothing to smash
print(lastStoneWeightBruteForce([3, 3])) // 0 — equal stones, both destroyed
print(lastStoneWeightBruteForce([])) // 0 — no stones at allBig-O: O(n² log n) — each of the up-to-n rounds destroys at least one stone, and each round pays O(n log n) to fully re-sort the remaining stones just to find the current top two.
Build a max-heap once. Each round, extract the two heaviest stones directly (O(log n) each), and push the difference back in if it's non-zero — no re-sorting required.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
func lastStoneWeight(_ stones: [Int]) -> Int {
var heap = Heap<Int>(sort: >) // max-heap: root is always the heaviest stone
for stone in stones {
heap.insert(stone)
}
while heap.count > 1 {
let first = heap.extract()!
let second = heap.extract()!
let diff = first - second
if diff > 0 {
heap.insert(diff)
}
}
return heap.peek ?? 0
}
// smoke test — same cases as the brute force
print(lastStoneWeight([2, 7, 4, 1, 8, 1])) // 1
print(lastStoneWeight([1])) // 1
print(lastStoneWeight([3, 3])) // 0
print(lastStoneWeight([])) // 0Big-O: O(n log n) total — n inserts to build the heap, plus at most n extract/insert pairs, each O(log n).
Re-sorting the entire array on every round wastes effort on ordering stones that never even come close to being smashed this round — the brute force pays O(n log n) to learn the full order every time, when it only ever needs to know the top two. A max-heap keeps the heaviest stone one peek away at all times and restores that property in O(log n) after each change, so the total cost tracks the number of smashes, not the number of comparisons needed to re-establish full order — that's what drops the overall complexity by a full factor of n.
-
Heaps and Priority Queues — the max-heap here is the same
Heap<T>structure, flipped to max-heap mode via the>comparator. - Top K and Heap Pattern — "repeatedly grab the current extreme" is this pattern's core move, just applied twice per round instead of once.
- Greedy — always smashing the two currently heaviest stones (rather than, say, planning ahead) is a greedy choice, and it happens to be provably optimal for this problem.
Last Stone Weight is a demolition derby judged by a max-heap — grab the two heaviest, let them collide, drop the survivor back in, and repeat until only rubble (or one stone) is left.
- Why does the optimal solution only push the difference back onto the heap
if diff > 0, and what would go wrong (or would anything?) if it always pushed the difference, including when it's0? - Trace
lastStoneWeight([3, 3])by hand — why does the final answer come out to0rather thannilor a crash? - Could you solve this problem with a min-heap instead of a max-heap by negating all the weights on the way in and out? Would that be more or less natural than using
sort: >directly?
⬅️ Previous: Kth Largest Element in a Stream · Next: K Closest Points to Origin ➡️