Skip to content

Volume ITechnology

4.17.2 — Last Stone Weight ​

LeetCode 1046 · Easy

The problem ​

Repeatedly take the two heaviest stones and smash them together. If they weigh the same, both are destroyed. If not, the heavier one is left with the difference. Return the weight of the last stone, or 0 if none remain.

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

8 and 7 → 1 left        [2, 4, 1, 1, 1]
4 and 2 → 2 left        [2, 1, 1, 1]
2 and 1 → 1 left        [1, 1, 1]
1 and 1 → both gone     [1]
→ 1

What the problem is really asking ​

Every round needs the two heaviest stones among those left. After the smash, a new stone may appear with a new weight, and it joins the pile. So the real question is: what structure hands you the largest item quickly, again and again, while new items keep arriving?

The pattern ​

The operation is always "give me the two largest", repeated. A structure that hands you the largest in O(\log n) and takes back a new value just as cheaply is a max-heap.

Sorting the array once does not work, because the leftover stone has a new weight and must be reinserted in order. You would re-sort after every smash, which is O(n^2 \log n).

The Python trick for a max-heap ​

heapq only gives you a min-heap. To get a max-heap, negate every value on the way in and on the way out.

python
heap = [-s for s in stones]      # negate
heapq.heapify(heap)
largest = -heapq.heappop(heap)   # negate back

The smallest negative number is the largest original, so a min-heap over negatives behaves as a max-heap.

Remember to negate on the way out. Forgetting is the standard bug, and it produces negative answers that look obviously wrong — which is at least a fast failure.

The solution ​

python
import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = [-s for s in stones]  # (1)
        heapq.heapify(heap)                      # (2) O(n)

        while len(heap) > 1:  # (3)
            first = -heapq.heappop(heap)         # (4) largest
            second = -heapq.heappop(heap)        # (5) second largest
            if first != second:  # (6)
                heapq.heappush(heap, -(first - second))

        return -heap[0] if heap else 0  # (7)
ts
// TypeScript has no built-in heap. MaxHeap is the MinHeap from 4.16 with the
// comparison flipped: pop() removes the largest, peek() reads it.
function lastStoneWeight(stones: number[]): number {
  const heap = new MaxHeap<number>();  // (1)
  for (const s of stones) heap.push(s);  // (2)

  while (heap.size > 1) {  // (3)
    const first = heap.pop()!;  // (4)
    const second = heap.pop()!;  // (5)
    if (first !== second) heap.push(first - second);  // (6)
  }

  return heap.size ? heap.peek()! : 0;  // (7)
}

The loop condition is > 1, not > 0. A smash needs two stones; one stone alone is the answer.

Nothing is pushed when the two are equal, because both stones are destroyed.

first >= second always, since the first pop gives the larger, so the difference is never negative and needs no abs.

Line by line ​

(1) Make every weight negative. Python's heapq only keeps the smallest item at the front. The most negative number belongs to the heaviest stone, so a heap of negated weights hands us the heaviest stone first.

(2) Arrange the list into heap order, in O(n).

(3) Keep going while at least two stones are left. A smash needs two.

(4) Take the heaviest stone, and negate it back to its real weight.

(5) Take the second heaviest.

(6) If they differ, the leftover stone goes back in. Its weight is first - second, which is positive, because first is the heavier one. We negate it again before pushing. If they are equal, both are destroyed and nothing goes back.

(7) Return the last stone's weight, or 0 if none is left. heap[0] is the front of the heap, still negated, so we negate it back.

Trace ​

Take stones = [2, 7, 4, 1, 8, 1]. The heap is shown with real weights, heaviest first.

RoundHeap beforeSmashPut backHeap after
18 7 4 2 1 18 and 714 2 1 1 1
24 2 1 1 14 and 222 1 1 1
32 1 1 12 and 111 1 1
41 1 11 and 1nothing1

One stone is left, so the loop stops. The answer is 1.

Complexity, derived ​

Time. Building the heap is O(n). Each round removes at least one stone, because two come out and at most one goes back. So there are at most n - 1 rounds. Each round does up to three heap operations, each O(\log n). The total is O(n \log n).

Space. The heap holds up to n weights, so O(n).

Edge cases ​

  • One stone. The loop never runs, and the answer is its weight.
  • Two equal stones. Both are destroyed, the heap is empty, and the answer is 0.
  • All stones equal and an even count. They destroy each other in pairs, and the answer is 0.

The bounded-values alternative ​

The constraints say stone weights are at most 1,000. When values are small and bounded, counting beats a heap — the same realisation as bucket sort in 4.4.5.

Keep an array of 1,001 counts and scan downwards for the two largest. Each scan is O(1001), a constant, so the total is O(n) with a large constant factor.

On these inputs the heap is faster in practice, because n is at most 30 and the constant on a 1,001-slot scan is much worse. What matters is not that counting wins here, but that you noticed the values were bounded and considered it. That habit is what makes the linear solutions in other problems findable.

Where this goes next ​

  • Minimum Cost to Connect Sticks — repeatedly combine the two smallest, and the total cost is the sum of the combinations. A min-heap, and it is exactly how Huffman coding builds its tree (Chapter 1.8).
  • Reorganize String and Task Scheduler — repeatedly take the most frequent item. 4.17.5.
  • Any greedy simulation where each step needs the current extreme.

The rule: when a loop repeatedly needs the largest or smallest of a changing collection, that is a heap. Sorting only works when the collection stops changing.

What the interviewer will push on ​

"Why not just sort?" The leftover stone has a new weight and must be reinserted in order, so you would re-sort every round.

"How do you get a max-heap in Python?" Negate on the way in and out.

"Why is the loop condition > 1?" A smash needs two stones.

"The weights are bounded — does that change anything?" Counting is possible, and say honestly why it does not help at n = 30.

One thing to volunteer: name Huffman coding when you mention the smallest-two variant. It shows the pattern is something you recognise rather than a one-off.

Next: 4.17.3 K Closest Points to Origin — a size-k heap again, but the other way round.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet