1046. Last Stone Weight (Easy)

Problem

You are given an array stones where each stone has a positive integer weight. Each round:

Take the two heaviest stones x, y (with x ≤ y).
If x == y, both are destroyed.
Otherwise, replace them with a stone of weight y - x.

Return the weight of the last remaining stone, or 0 if none remain.

Example

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

LeetCode 1046 · Link · Easy

Worked traces

The algorithm only ever cares about the two largest weights at each step. Watching the heap shrink (or annihilate) round by round is the fastest way to see why a max-heap is the natural fit. Each row below shows the multiset of stones (sorted descending for readability) and the action taken.

Trace 1: `[2,7,4,1,8,1]` → `1` (the canonical case)

heap (desc)        action                       result        size
[8,7,4,2,1,1]      pop 8,7  →  push 1          [4,2,1,1,1]   5
[4,2,1,1,1]        pop 4,2  →  push 2          [2,1,1,1,1]   4
[2,1,1,1,1]        pop 2,1  →  push 1          [1,1,1,1]     3
[1,1,1,1]          pop 1,1  →  destroy         [1,1]         1

Returns 1. The trick is that an annihilation step removes two elements, not one, so the size jumps by 2 instead of 1.

Trace 2: `[31,26,33,21,40]` → `9` (no annihilations)

When all the differences are nonzero, the heap shrinks by exactly one per round and the final survivor is whatever weight is left after n - 1 subtractions.

heap (desc)        action                       result
[40,33,31,26,21]   pop 40,33  →  push 7        [31,26,21,7]
[31,26,21,7]       pop 31,26  →  push 5        [21,7,5]
[21,7,5]           pop 21,7   →  push 14       [14,5]
[14,5]             pop 14,5   →  push 9        [9]

Returns 9. Five stones, four rounds, one survivor.

Trace 3: `[9,3,2,10]` → `0` (chain of annihilations)

Pairs that happen to be equal vanish entirely. With a small input, two consecutive annihilations can clear the heap completely.

heap (desc)        action                       result
[10,9,3,2]         pop 10,9  →  push 1         [3,2,1]
[3,2,1]            pop 3,2   →  push 1         [1,1]
[1,1]              pop 1,1   →  destroy        []

Returns 0. Notice how the two pushed 1s collide in the next round, an emergent property the algorithm doesn’t plan for; it just falls out of always taking the two largest.

What the traces reveal

The only state that matters is the multiset of weights. Order, history, and identity are irrelevant. That’s the signature of a problem that wants a heap.
Each round is $O(log n)$ reads + $O(log n)$ writes. Three operations on a heap (two pops, optional push), no scanning, no indexing.
The algorithm never looks ahead. It can’t tell whether a push will produce an annihilation later. Greedy on the two largest is enough.

Try it yourself

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, sort each round

Each round, re-sort the whole array, pop the two largest off the end, compute the remainder, append it back.

def last_stone_weight(stones):
    while len(stones) > 1:    # L1: outer loop, runs up to n-1 times
        stones.sort()         # L2: O(n log n) per round
        y = stones.pop()      # L3: O(1) (pop from end)
        x = stones.pop()      # L4: O(1) (pop from end)
        if x != y:
            stones.append(y - x)  # L5: O(1) amortized
    return stones[0] if stones else 0

function lastStoneWeight(stones: number[]): number {
    const arr = [...stones];
    while (arr.length > 1) {         // L1: outer loop, runs up to n-1 times
        arr.sort((a, b) => a - b);   // L2: O(n log n) per round
        const y = arr.pop()!;        // L3: O(1) (pop from end)
        const x = arr.pop()!;        // L4: O(1) (pop from end)
        if (x !== y)
            arr.push(y - x);         // L5: O(1) amortized
    }
    return arr.length > 0 ? arr[0] : 0;
}

import "sort"

func lastStoneWeight(stones []int) int {
    arr := make([]int, len(stones))
    copy(arr, stones)
    for len(arr) > 1 {           // L1: outer loop, runs up to n-1 times
        sort.Ints(arr)           // L2: O(n log n) per round
        y := arr[len(arr)-1]    // L3: O(1) pop from end
        x := arr[len(arr)-2]    // L4: O(1) pop from end
        arr = arr[:len(arr)-2]
        if x != y {
            arr = append(arr, y-x) // L5: O(1) amortized
        }
    }
    if len(arr) > 0 { return arr[0] }
    return 0
}

final class Solution {
    func lastStoneWeight(_ stones: [Int]) -> Int {
        var values = stones
        while values.count > 1 {
            values.sort()
            let first = values.removeLast()
            let second = values.removeLast()
            if first != second { values.append(first - second) }
        }
        return values.first ?? 0
    }
}

Where the time goes, line by line

Variables: n = number of stones in the input array.

Line	Per-call cost	Times executed	Contribution
L1 (loop test)	$O(1)$	n-1	$O(n)$
L2 (sort)	$O(n log n)$	up to n-1	$O(n² log n)$ ← dominates
L3, L4 (pops)	$O(1)$ each	n-1 each	$O(n)$
L5 (append)	$O(1)$ amortized	up to n-1	$O(n)$

The whole story is L2. Sorting an array of size n costs $O(n log n)$ , and we do it once per round. Annihilation rounds shrink the array faster, but the worst case (no annihilations) still gives n-1 rounds, so the total is $O(n × n log n)$ = $O(n² log n)$ .

Complexity

Time: $O(n² log n)$ , driven entirely by L2.
Space: $O(1)$ extra (sort is in-place; pops and appends don’t grow the array beyond its starting capacity).

Approach 2: Max-heap (optimal)

Python’s heapq is a min-heap. Negate every weight on the way in and out and you get a max-heap for free. TypeScript has no built-in heap, so the approach file includes a small MaxHeap class.

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]            # L1: O(n)
    heapq.heapify(heap)                    # L2: O(n) (Floyd's bottom-up)
    while len(heap) > 1:                   # L3: outer loop, up to n-1 rounds
        y = -heapq.heappop(heap)           # L4: O(log n) per call
        x = -heapq.heappop(heap)           # L5: O(log n) per call
        if x != y:
            heapq.heappush(heap, -(y - x)) # L6: O(log n) when taken
    return -heap[0] if heap else 0

class MaxHeap {
    private data: number[] = [];
    get size(): number { return this.data.length; }
    push(val: number): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    pop(): number {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) { this.data[0] = last; this._siftDown(0); }
        return top;
    }
    peek(): number { return this.data[0]; }
    private _siftUp(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p] >= this.data[i]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p;
        }
    }
    private _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let largest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] > this.data[largest]) largest = l;
            if (r < n && this.data[r] > this.data[largest]) largest = r;
            if (largest === i) break;
            [this.data[largest], this.data[i]] = [this.data[i], this.data[largest]]; i = largest;
        }
    }
}

function lastStoneWeight(stones: number[]): number {
    const heap = new MaxHeap();
    for (const s of stones) heap.push(s);  // L1+L2: build max-heap O(n)
    while (heap.size > 1) {                // L3: outer loop, up to n-1 rounds
        const y = heap.pop();              // L4: O(log n) per call
        const x = heap.pop();              // L5: O(log n) per call
        if (x !== y)
            heap.push(y - x);             // L6: O(log n) when taken
    }
    return heap.size > 0 ? heap.peek() : 0;
}

package main

import (
    "container/heap"
    "fmt"
)

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 any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

func lastStoneWeight(stones []int) int {
    h := make(MaxHeap, len(stones))
    copy(h, stones)
    heap.Init(&h)                        // L1+L2: O(n) build max-heap
    for h.Len() > 1 {                    // L3: outer loop, up to n-1 rounds
        y := heap.Pop(&h).(int)          // L4: O(log n) pop largest
        x := heap.Pop(&h).(int)          // L5: O(log n) pop second largest
        if x != y { heap.Push(&h, y-x) } // L6: O(log n) push remainder
    }
    if h.Len() > 0 { return h[0] }
    return 0
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    assert(lastStoneWeight([]int{2, 7, 4, 1, 8, 1}) == 1)
    assert(lastStoneWeight([]int{1}) == 1)
    assert(lastStoneWeight([]int{31, 26, 33, 21, 40}) == 9)
    assert(lastStoneWeight([]int{9, 3, 2, 10}) == 0)
    assert(lastStoneWeight([]int{2, 2}) == 0)
    assert(lastStoneWeight([]int{1, 3}) == 2)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class Solution {
    func lastStoneWeight(_ stones: [Int]) -> Int {
        var heap = BinaryHeap<Int>(hasHigherPriority: >)
        for stone in stones { heap.insert(stone) }
        while heap.count > 1 {
            let first = heap.removeRoot()!
            let second = heap.removeRoot()!
            if first != second { heap.insert(first - second) }
        }
        return heap.removeRoot() ?? 0
    }
}

Where the time goes, line by line

Variables: n = number of stones in the input array.

Line	Per-call cost	Times executed	Contribution
L1 (negate list / build heap)	$O(1)$ per element	n	$O(n)$
L2 (heapify / incremental)	$O(n)$	1	$O(n)$
L3 (loop test)	$O(1)$	n-1	$O(n)$
L4, L5 (pops)	$O(log n)$	n-1 each	$O(n log n)$ ← dominates
L6 (push)	$O(log n)$	up to n-1	$O(n log n)$

Two important details that often trip people up:

heapify is $O(n)$ , not $O(n log n)$ . Floyd’s bottom-up construction sifts each node down toward the leaves, and the total work across the whole tree is bounded by a geometric series that sums to $O(n)$ . Building the heap is cheaper than maintaining it.
Each round does at most three $O(log n)$ operations. Two pops, one optional push. We never scan, never re-sort, never index into the middle.

Since we do n-1 rounds and each round is $O(log n)$ , the running total is $O(n log n)$ , dominated by L4/L5/L6.

Complexity

Time: $O(n log n)$ , driven by L4/L5/L6 (the three heap operations inside the loop).
Space: $O(n)$ for the heap.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Bottleneck
Sort each round	$O(n² log n)$	$O(1)$	L2: re-sorting every round
Max-heap	$O(n log n)$	$O(n)$	L4/L5/L6: per-round heap ops

Simulation problems with dynamic priority almost always want a heap. The brute-force version is a good baseline because it makes the “what does each round actually cost?” question impossible to ignore: if your inner-loop step is $O(n log n)$ , you’ve already lost a factor of n that a heap would have saved.

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        y = -heapq.heappop(heap)
        x = -heapq.heappop(heap)
        if x != y:
            heapq.heappush(heap, -(y - x))
    return -heap[0] if heap else 0

def _run_tests():
    assert last_stone_weight([2, 7, 4, 1, 8, 1]) == 1     # canonical: ends at 1
    assert last_stone_weight([1]) == 1                     # single stone
    assert last_stone_weight([31, 26, 33, 21, 40]) == 9    # no annihilations
    assert last_stone_weight([9, 3, 2, 10]) == 0           # chain of annihilations
    assert last_stone_weight([2, 2]) == 0                  # immediate annihilation
    assert last_stone_weight([1, 3]) == 2                  # one round, no destroy
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses the MaxHeap approach (Approach 2).
// See 1046-last-stone-weight-approach2.ts for the full implementation.
const heap = new MaxHeap();
[2, 7, 4, 1, 8, 1].forEach(s => heap.push(s));
// ... run lastStoneWeight on each case
console.assert(lastStoneWeight([2, 7, 4, 1, 8, 1]) === 1);
console.assert(lastStoneWeight([1]) === 1);
console.assert(lastStoneWeight([31, 26, 33, 21, 40]) === 9);
console.assert(lastStoneWeight([9, 3, 2, 10]) === 0);
console.assert(lastStoneWeight([2, 2]) === 0);
console.assert(lastStoneWeight([1, 3]) === 2);
console.log("all tests pass");

Heaps / Priority Queues, max-heap via negated min-heap

Heap and Priority Queue, the priority frontier for repeatedly taking the smallest, largest, or most urgent item.
Simulation, the explicit state model for executing rules exactly while keeping cases organized.