What pattern does Last Stone Weight use?

The Pattern: Heap / Priority Queue (Max Heap Simulation) The Heuristic: When a problem requires repeatedly extracting and updating the largest or smallest elements dynamically, simulate a max heap using a min heap with negated values to achieve efficient O(log n) operations.

Last Stone Weight — Heap / Priority Queue

Q: What is the time complexity of Last Stone Weight?

O(n log n). Building the heap takes O(n). Each smash operation involves two pops and possibly one push, each O(log n). Since there are at most n-1 smashes, total complexity is O(n log n).

Problem

Given an array of integers stones representing the weights of stones, repeatedly smash the two heaviest stones until at most one stone remains, and return the weight of the remaining stone or 0 if none remain.

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

Example

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

Output: 1

Initially, the two heaviest stones are 8 and 7. Smashing them yields a stone of weight 1 (8 - 7). The stones become [2,4,1,1,1]. Next, the two heaviest stones are 4 and 2. Smashing them yields 2 (4 - 2). The stones become [2,1,1,1]. Then, the two heaviest stones are 2 and 1. Smashing them yields 1 (2 - 1). The stones become [1,1,1]. Next, the two heaviest stones are 1 and 1. Smashing them destroys both. The stones become [1]. Only one stone remains with weight 1, which is returned.

Approach

Straightforward Solution

A brute-force approach would repeatedly sort the stones array to find the two heaviest stones, resulting in O(n log n) sorting per iteration and O(n² log n) overall time complexity, which is inefficient.

Core Observation

At each step, the two heaviest stones must be selected and smashed. This requires efficient retrieval of the maximum elements repeatedly, which suggests using a max heap data structure.

Path to Optimal

Preview

The key recognition signals are 'repeatedly select the two heaviest stones' and 'update the collection dynamically'. These indicate a heap or priority queue pattern because heaps provide O(log n) insertion and extraction of maximum elements…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Transform the stones array into a max heap by negating the values (since Python's heapq is a min heap). Repeatedly pop the two largest stones, smash them, and if the result is non-zero, push it back into the heap…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Building the heap takes O(n). Each smash operation involves two pops and possibly one push, each O(log n). Since there are at most n-1 smashes, total complexity is O(n log n).

Space

O(n)

The heap stores all stones, requiring O(n) auxiliary space proportional to the input size.

Solution

Python

1import heapq
2
3class Solution:
  def lastStoneWeight(self, stones: list[int]) -> int:
      max_heap = [-s for s in stones]
      heapq.heapify(max_heap)
7
      while len(max_heap) > 1:
          first = heapq.heappop(max_heap)
          second = heapq.heappop(max_heap)
          if second > first:
              heapq.heappush(max_heap, first - second)
      
      max_heap.append(0)
      return abs(max_heap[0])

Step-by-Step Solution

1

Build a Max Heap by Negating Stone Weights

5max_heap = [-s for s in stones]
6heapq.heapify(max_heap)

Objective

To create a max heap from the stones array by negating the values and heapifying.

Key Insight

Python's heapq module implements a min heap, so negating the stone weights transforms the problem into a min heap of negative values, effectively simulating a max heap. This allows efficient extraction of the largest stones using heap operations.

Interview Quick-Check

Core Logic

Negating values transforms the problem into a min heap of negative numbers, enabling max heap behavior with Python's heapq.

Common Pitfalls & Bugs

Forgetting to negate values leads to extracting the smallest stones instead of the largest, breaking the logic.

2

Simulate Stone Smashing by Extracting and Combining the Two Largest Stones

To repeatedly extract the two largest stones, smash them, and push the difference back if non-zero.

3

Handle the Final Stone or Return Zero if None Remain

To return the weight of the last remaining stone or zero if no stones remain.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 5 Critical

max_heap = [-s for s in stones]

Create a list of negated stone weights to simulate a max heap using Python's min heap.

Negating the stone weights transforms the problem into a min heap of negative values, allowing efficient extraction of the largest stones using heapq, which only supports min heaps.

Line 9 Critical

first = heapq.heappop(max_heap)

Extract the largest stone (smallest negative value) from the heap.

Popping the smallest negative value corresponds to removing the heaviest stone, which is essential for simulating the stone smashing process correctly.

Line 10 Critical

second = heapq.heappop(max_heap)

Extract the second largest stone from the heap.

Removing the second heaviest stone allows the algorithm to simulate the smash between the two largest stones at each iteration.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why is a max heap (or simulated max heap) the appropriate data structure for this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Last Stone Weight from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Last Stone Weight drill

or drill a free problem

1	`import heapq`
2
3	`class Solution:`
4	`def lastStoneWeight(self, stones: list[int]) -> int:`
5	`max_heap = [-s for s in stones]`
6	`heapq.heapify(max_heap)`
7
8	`while len(max_heap) > 1:`
9	`first = heapq.heappop(max_heap)`
10	`second = heapq.heappop(max_heap)`
11	`if second > first:`
12	`heapq.heappush(max_heap, first - second)`
13
14	`max_heap.append(0)`
15	`return abs(max_heap[0])`