DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Last Stone Weight

easyHeaps and top-K

Problem statement

You have a pile of stones, each with a positive integer weight. Repeat the following while at least two stones remain: take the two heaviest stones, with weights y >= x, and smash them together.

  • If x == y, both stones are destroyed.
  • Otherwise the lighter stone is destroyed and the heavier one is left with weight y - x, and goes back into the pile.

Return the weight of the last stone left, or 0 if no stones remain.

Examples

Example 1

Input: stones = [6, 3, 9, 2]

Output: 2

Explanation: 9 and 6 leave a 3, so the pile is [3, 3, 2]. The two 3s destroy each other, leaving only 2.

Example 2

Input: stones = [5, 5]

Output: 0

Explanation: Two equal stones destroy each other and nothing is left.

Hints

Approach

Simulate with a max-heap.

  1. Put every weight into a max-heap. In Python, store -weight in heapq so the largest weight becomes the smallest key.
  2. While the heap has two or more stones, pop the heaviest y and the next x.
  3. If y != x, push y - x back.
  4. Return the remaining weight, or 0 if the heap is empty.

Each round is a couple of O(log n) heap operations instead of a sort.

ComplexityTime O(n log n)Space O(n)
Python
import heapq
class Solution:
def lastStoneWeight(self, stones: list[int]) -> int:
heap = [-s for s in stones] # heapq is a min-heap, so store negatives
heapq.heapify(heap)
while len(heap) > 1:
y = -heapq.heappop(heap) # heaviest
x = -heapq.heappop(heap) # second heaviest
if y != x:
heapq.heappush(heap, -(y - x))
return -heap[0] if heap else 0

Follow-up questions

  • Return the order in which stones were destroyed.
  • You may choose which two stones to smash each time. What is the smallest possible final weight?

Frequently asked questions

heapq only provides a min-heap: the smallest item is at index 0. Storing -weight makes the heaviest stone the smallest key. Remember to negate again when you pop and when you return the answer.

Not here, because the rules fix which stones are smashed. The heap is just a fast way to follow those rules. The related Last Stone Weight II lets you choose the pairs, and that becomes a subset-sum dynamic programming problem.

It is a gentle introduction to "always process the largest item next", which is how you drain the biggest queue first, reclaim space from the largest files first, or schedule the heaviest job first. The heap keeps that ordering cheap as items change.