What is the brute force approach and complexity for Last Stone Weight?

Sort the pile each turn and smash the two heaviest at the back with time complexity O(N² log N) and space complexity O(1).

What is the optimal approach and complexity for Last Stone Weight?

Keep the stones in a max-heap; pop the two heaviest, push the difference with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Last Stone Weight?

Look for key signals in the prompt: "the two heaviest stones" indicates We need the current maximum, twice per turn. The maximum changes after every turn, so the structure must update fast.; "a new stone of weight y − x" indicates The pile changes by one insert per turn. A heap takes one insert in O(log n) without re-sorting.; "until one stone is left" indicates Keep looping on the size of the pile, not on a fixed count..

Last Stone Weight

Easy·LeetCode #1046Basic Anchor

LeetCode

Jump:

30-Second Mental ModelHeap — Kth element (max-heap of everything, take the top each turn)

Complexity:O(N² log N)→O(N log N)

Key Insight

A max-heap gives the heaviest stone in O(log N). Pop the two heaviest. If they differ, push back their difference. The pile is never sorted as a whole.

Core Validity Invariant

The top of the max-heap is always the heaviest remaining stone, so the two pops are always the two stones the rule asks for. The heap re-orders itself after every push and pop, so this stays true for the whole game.

Problem

You have a pile of stones. Stone i weighs stones[i].

Repeat this while two or more stones are left:

Take the two heaviest stones. Call the heavier one y and the lighter one x.
If x == y, both stones are destroyed.
If x != y, the lighter stone is destroyed and the heavier one now weighs y − x.

When one stone is left, return its weight. If no stones are left, return 0.

Input

stones, a list of stone weights.

Output

The weight of the last stone, or 0 if none is left.

Example 1

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

Output: 1

7 and 8 → 1, so the pile is [2, 4, 1, 1, 1]. Then 4 and 2 → 2, pile [2, 1, 1, 1]. Then 2 and 1 → 1, pile [1, 1, 1]. Then 1 and 1 are equal, so both are destroyed. One stone (weight 1) is left.

Example 2

Input: stones = [1]

Output: 1

There is only one stone, so it is the last one.

Constraints

• 1 ≤ stones.length ≤ 30
• 1 ≤ stones[i] ≤ 1000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Each turn I need the two heaviest stones. Which data structure gives me the largest item quickly?
2.
After a smash, the new stone can land anywhere in the weight order. Does that break a list I already sorted?
3.
Each turn removes two stones and adds at most one. How many turns can happen at most?
4.
What should the answer be when every stone is destroyed?
5.
If I sort the pile once, what must I do after each smash to keep it correct?

Brute force approach

Idea

Each turn, sort the stones from lightest to heaviest. The two heaviest are the last two. Smash them, put the new stone (if any) back into the list, and repeat.

Thinking process

1
The rule always uses the two heaviest stones, so each turn I need them at the end of a sorted list.
2
Take [2, 7, 4, 1, 8, 1]. Sorted: [1, 1, 2, 4, 7, 8]. The last two are 7 and 8, and 8 − 7 = 1 goes back: [1, 1, 2, 4, 1].
3
Sort again: [1, 1, 1, 2, 4]. The new stone could land anywhere, so the whole list has to be sorted again.
4
Keep going while at least two stones are left. When one is left, return it. If none is left, return 0.

Code & Implementation

brute.cpp

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // Smash until at most one stone is left.
        while (stones.size() > 1) {
            // Sort the whole pile every turn (ascending),
            // so the two heaviest stones sit at the back.
            sort(stones.begin(), stones.end());
            int heavy = stones.back(); stones.pop_back();
            int light = stones.back(); stones.pop_back();
            // If they differ, the heavier stone is left with the difference.
            if (heavy != light) stones.push_back(heavy - light);
        }
        return stones.empty() ? 0 : stones[0];
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> list = new ArrayList<>();
        for (int s : stones) {
            list.add(s);
        }

        // Smash until at most one stone is left.
        while (list.size() > 1) {
            // Sort the whole pile every turn (ascending),
            // so the two heaviest stones sit at the back.
            Collections.sort(list);
            int heavy = list.remove(list.size() - 1);
            int light = list.remove(list.size() - 1);
            // If they differ, the heavier stone is left with the difference.
            if (heavy != light) {
                list.add(heavy - light);
            }
        }
        return list.isEmpty() ? 0 : list.get(0);
    }
}

from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Smash until at most one stone is left.
        while len(stones) > 1:
            # Sort the whole pile every turn (ascending),
            # so the two heaviest stones sit at the back.
            stones.sort()
            heavy = stones.pop()
            light = stones.pop()
            # If they differ, the heavier stone is left with the difference.
            if heavy != light:
                stones.append(heavy - light)
        return stones[0] if stones else 0

export function lastStoneWeight(stones: number[]): number {
    const pile = [...stones];
    // Smash until at most one stone is left.
    while (pile.length > 1) {
        // Sort the whole pile every turn (ascending),
        // so the two heaviest stones sit at the back.
        pile.sort((a, b) => a - b);
        const heavy = pile.pop()!;
        const light = pile.pop()!;
        // If they differ, the heavier stone is left with the difference.
        if (heavy !== light) {
            pile.push(heavy - light);
        }
    }
    return pile.length === 0 ? 0 : pile[0];
}

Complexity

Time O(N² log N)Space O(1)

There are at most N − 1 turns, and each turn sorts the whole pile again. After one smash the pile is almost sorted already, but the brute force sorts it from scratch.

Better approach

Why brute force is slow

Brute force sorts the whole pile every turn, even though only one stone is new since the last sort.

What repeated work are we doing?

Each turn re-sorts a list that was already sorted, apart from one new stone.

What information can we reuse?

Keep the list sorted. Find the new stone's spot with binary search (log N), then shift the heavier stones one step. No full sort is needed.

New approach

Idea

Sort the pile once at the start. Each turn the two heaviest are at the back, so pop them off. If a new stone is made, find its spot with binary search and insert it there. The list stays sorted, so it is never sorted again.

Thinking process

1
After one smash the list is sorted except for one new stone. Sorting everything again is wasted work.
2
Take [1, 1, 2, 4, 7, 8]. Pop 8 and 7 from the back. The new stone is 1, and the rest is [1, 1, 2, 4]. Binary search says 1 goes at index 0, so insert it: [1, 1, 1, 2, 4].
3
The heaviest stone is always at the back, so the two heaviest are always two pops away.
4
The insert still shifts every stone heavier than the new one, so one insert can cost up to N moves.

Code & Implementation

better.cpp

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // Sort once, ascending: the heaviest stone is always at the back.
        sort(stones.begin(), stones.end());
        while (stones.size() > 1) {
            int heavy = stones.back(); stones.pop_back();
            int light = stones.back(); stones.pop_back();
            if (heavy != light) {
                // Put the new stone back in sorted order:
                // binary search finds the spot, insert shifts the bigger stones.
                int d = heavy - light;
                stones.insert(lower_bound(stones.begin(), stones.end(), d), d);
            }
        }
        return stones.empty() ? 0 : stones[0];
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> list = new ArrayList<>();
        for (int s : stones) {
            list.add(s);
        }

        // Sort once, ascending: the heaviest stone is always at the back.
        Collections.sort(list);
        while (list.size() > 1) {
            int heavy = list.remove(list.size() - 1);
            int light = list.remove(list.size() - 1);
            if (heavy != light) {
                // Put the new stone back in sorted order:
                // binary search finds the spot, insert shifts the bigger stones.
                int d = heavy - light;
                int idx = Collections.binarySearch(list, d);
                if (idx < 0) {
                    idx = -(idx + 1);
                }
                list.add(idx, d);
            }
        }
        return list.isEmpty() ? 0 : list.get(0);
    }
}

import bisect
from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Sort once, ascending: the heaviest stone is always at the back.
        stones.sort()
        while len(stones) > 1:
            heavy = stones.pop()
            light = stones.pop()
            if heavy != light:
                # Put the new stone back in sorted order:
                # binary search finds the spot, insert shifts the bigger stones.
                d = heavy - light
                bisect.insort(stones, d)
        return stones[0] if stones else 0

export function lastStoneWeight(stones: number[]): number {
    const pile = [...stones];
    // Sort once, ascending: the heaviest stone is always at the back.
    pile.sort((a, b) => a - b);
    while (pile.length > 1) {
        const heavy = pile.pop()!;
        const light = pile.pop()!;
        if (heavy !== light) {
            // Put the new stone back in sorted order:
            // binary search finds the spot, insert shifts the bigger stones.
            const d = heavy - light;
            let lo = 0;
            let hi = pile.length;
            while (lo < hi) {
                const mid = (lo + hi) >> 1;
                if (pile[mid] < d) lo = mid + 1;
                else hi = mid;
            }
            pile.splice(lo, 0, d);
        }
    }
    return pile.length === 0 ? 0 : pile[0];
}

Complexity

Time O(N²)Space O(1)

At most N − 1 turns. Each turn does one binary search (log N) and one shift of up to N stones, so O(N) per turn.

Optimized approach

Idea

A max-heap gives the heaviest stone in O(log N). Pop the two heaviest. If they differ, push back their difference. The pile is never sorted as a whole.

Start from brute force

Brute force sorts the whole pile on every turn, only to read the two heaviest stones at the end.

Find the repeated work

After one smash the pile changes by two removals and at most one insert, yet the whole order is rebuilt. The rule only ever needs the maximum, so the full order is wasted work.

Define the state — what variables do I need?

pile (max-heap): All remaining stones. Its top is always the heaviest one.
heavy, light: The two stones popped this turn. heavy is never lighter than light.
answer: The one stone left at the end (the top of the heap), or 0 if the heap is empty.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Start

Push all stones into a max-heap

A heap puts the heaviest stone on top without sorting the whole pile.

The heap holds 2 or more stones

heavy = top, then pop; light = top, then pop

The top is the maximum, so these are the two heaviest stones, which is exactly what the rule uses.

heavy ≠ light

push(heavy − light)

The lighter stone is gone, and the heavier one now weighs heavy − light. That value is positive, because heavy is the larger one.

heavy = light

push nothing

Both stones are destroyed, so there is nothing new to add.

The heap holds 1 or 0 stones

stop; return the top, or 0 if the heap is empty

This is the last stone, or no stone is left.

What does the current window add to the answer?

There is no running total. The answer is the one stone that survives, or 0 if the pile is empty.

Code & Implementation

optimal.cpp

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // Max-heap: top() is always the heaviest stone.
        priority_queue<int> pile(stones.begin(), stones.end());
        while (pile.size() > 1) {
            int heavy = pile.top(); pile.pop();
            int light = pile.top(); pile.pop();
            // Equal stones destroy each other; otherwise the heavier one shrinks.
            if (heavy != light) pile.push(heavy - light);
        }
        return pile.empty() ? 0 : pile.top();
    }
};

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

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Max-heap: peek() is always the heaviest stone.
        PriorityQueue<Integer> pile = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) {
            pile.add(s);
        }
        while (pile.size() > 1) {
            int heavy = pile.poll();
            int light = pile.poll();
            // Equal stones destroy each other; otherwise the heavier one shrinks.
            if (heavy != light) {
                pile.add(heavy - light);
            }
        }
        return pile.isEmpty() ? 0 : pile.peek();
    }
}

import heapq
from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Max-heap: top is always the heaviest stone (negated in Python min-heap).
        pile = [-s for s in stones]
        heapq.heapify(pile)
        while len(pile) > 1:
            heavy = -heapq.heappop(pile)
            light = -heapq.heappop(pile)
            # Equal stones destroy each other; otherwise the heavier one shrinks.
            if heavy != light:
                heapq.heappush(pile, -(heavy - light))
        return -pile[0] if pile else 0

class MaxHeap {
    private data: number[] = [];

    constructor(items: number[] = []) {
        for (const item of items) {
            this.push(item);
        }
    }

    push(val: number): void {
        this.data.push(val);
        this.bubbleUp(this.data.length - 1);
    }

    pop(): number | undefined {
        if (this.data.length === 0) return undefined;
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): number | undefined {
        return this.data[0];
    }

    size(): number {
        return this.data.length;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.data[parent] < this.data[idx]) {
                [this.data[parent], this.data[idx]] = [this.data[idx], this.data[parent]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.data.length;
        while (true) {
            let largest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.data[left] > this.data[largest]) largest = left;
            if (right < len && this.data[right] > this.data[largest]) largest = right;
            if (largest !== idx) {
                [this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
                idx = largest;
            } else {
                break;
            }
        }
    }
}

export function lastStoneWeight(stones: number[]): number {
    // Max-heap: top() is always the heaviest stone.
    const pile = new MaxHeap(stones);
    while (pile.size() > 1) {
        const heavy = pile.pop()!;
        const light = pile.pop()!;
        // Equal stones destroy each other; otherwise the heavier one shrinks.
        if (heavy !== light) {
            pile.push(heavy - light);
        }
    }
    return pile.size() === 0 ? 0 : pile.peek()!;
}

Complexity

Time O(N log N)Space O(N)

Building the heap is O(N). Then at most N − 1 turns, each with two pops and at most one push on a heap of size at most N, so O(log N) each. The heap holds a copy of the stones, so the space is O(N).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Sort the pile each turn and smash the two heaviest at the back	O(N² log N)	O(1)
Better	Sort once; after each smash, insert the new stone at its sorted spot	O(N²)	O(1)
Optimal	Keep the stones in a max-heap; pop the two heaviest, push the difference	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“the two heaviest stones”We need the current maximum, twice per turn. The maximum changes after every turn, so the structure must update fast.
“a new stone of weight y − x”The pile changes by one insert per turn. A heap takes one insert in O(log n) without re-sorting.
“until one stone is left”Keep looping on the size of the pile, not on a fixed count.

Repeatedly take the largest item+items change one at a time+max-heap of all items→Heap — Kth element (max-heap of everything, take the top each turn)

This is the anchor of the Kth element sub-pattern. The heap holds the whole pile, not just K items, because the pile keeps changing after each turn. The next questions keep only K items in a heap, which is where the size limit of K comes in.

Don't make this mistake

Min-heap instead of max-heap (pattern confusion)

✗ priority_queue<int, vector<int>, greater<int>> pile(stones.begin(), stones.end());

✓ priority_queue<int> pile(stones.begin(), stones.end());

greater<int> puts the lightest stone on top, so each turn smashes the two lightest stones. On the dry-run [2, 7, 4, 1, 8, 1] the min-heap pops 1 and 1 first (equal, both gone), then 2 and 4 (push 2), then 2 and 7 (push 5), then 5 and 8 (push 3). It returns 3. The correct answer is 1.

Reading top() of an empty heap

✗ return pile.top();

✓ return pile.empty() ? 0 : pile.top();

The input [2, 2] destroys both stones, so the heap is empty when the loop ends. top() on an empty priority_queue is undefined behaviour, usually a crash. The answer should be 0.

Keeping a sorted list but not inserting the new stone

✗ sort(...) once, then pop_back two stones and push_back(diff) at the end

✓ insert the new stone at its sorted spot, or use a heap

On the dry-run, after 8 and 7 are smashed, the pile is [1, 1, 2, 4, 1] because the new 1 was put at the end. The last two are then 1 and 4, but the real two heaviest are 4 and 2. The list is no longer sorted, so the wrong pair gets smashed.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Heap — Top K translate into production architectures and low-level memory mechanics.

LLD Real-World Story

High-Frequency Trading (HFT) Order Book

Price-time priority matching engine powered by heap buckets and tree maps.

Explore Track

C++ Internals

STL Containers & Allocator Internals

std::priority_queue container adapter and underlying heapify memory buffers.

Explore Track

K Largest Elements