Skip to main content
DSA patterns

Last Stone Weight

easyHeaps and top-K Must-doAmazonTCSAccenture

Problem statement

You're given a list of stone weights. Repeatedly take the two heaviest stones and smash them together: if they weigh the same, both are destroyed; otherwise the lighter one is destroyed and the heavier one is left with a new weight equal to the difference between the two.

Keep going until at most one stone is left. Return that stone's weight, or 0 if none remain.

Examples

Example 1

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

Output: 1

Explanation: smashing 8 and 7 leaves a 1, giving [2, 4, 1, 1, 1]. Smashing 4 and 2 leaves a 2, giving [2, 1, 1, 1]. Smashing 2 and 1 leaves a 1, giving [1, 1, 1]. Smashing the last two 1s cancels them out entirely, leaving [1] — the answer.

Example 2

Input: stones = [1]

Output: 1

Explanation: with only one stone, there's nothing to smash it against, so it's already the answer.

Hints

Hint 1: At every step you only care about the two heaviest stones — nothing about the rest of the pile matters until the next round.

Approach

Optimal: Max-heap

Intuition

A max-heap keeps the largest value reachable in O(1) and lets you remove or insert a value in O(log n), without ever needing to touch the rest of the pile. That's exactly what this problem repeats over and over: grab the two biggest, remove them, maybe put one value back. Most languages (Python included) only provide a min-heap, so the standard trick is to store every weight as its negative — the "smallest" negative number is then the heaviest actual stone.

Steps

  1. Push the negative of every stone's weight into a heap (making it act like a max-heap).
  2. While more than one value remains: pop the two smallest (most negative) values, first and second — these represent the two heaviest stones.
  3. If they're unequal, push the negative of their difference back in.
  4. Repeat from step 2.
  5. If the heap is empty, return 0; otherwise return the absolute value of what's left.

Dry run

stones = [2, 7, 4, 1, 8, 1] → heap holds [-8, -7, -4, -2, -1, -1] (conceptually; the actual heap order isn't fully sorted, but pops always return the most negative first).

round pop first, second smash push back heap (heaviest → lightest, conceptually)
1 -8, -7 8 vs 7 -(8-7) = -1 [-4, -2, -1, -1, -1]
2 -4, -2 4 vs 2 -(4-2) = -2 [-2, -1, -1, -1]
3 -2, -1 2 vs 1 -(2-1) = -1 [-1, -1, -1]
4 -1, -1 1 vs 1 equal, nothing pushed [-1]

One value left: -1, so the answer is abs(-1) = 1.

Edge cases: a single stone never enters the loop, so the heap still holds exactly one value at the end. If every stone cancels out, the heap ends up empty and the answer is 0.

Complexity

Time O(n log n) - Building the heap from n stones costs O(n). Each round pops twice and pushes at most once, each of those O(log n), and there are at most n rounds, giving O(n log n) overall.

Space O(n) - The heap holds up to n stones at once.

import heapq


class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)

        while len(heap) > 1:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if y != x:
                heapq.heappush(heap, -(y - x))

        return -heap[0] if heap else 0


if __name__ == "__main__":
    print(Solution().lastStoneWeight([2, 7, 4, 1, 8, 1]))  # 1
    print(Solution().lastStoneWeight([1]))  # 1
RecapThe whole problem in a few lines, for the night before
  • Spot it: "repeatedly take the two biggest, combine or cancel them" — a max-heap pattern
  • Idea: push everything into a max-heap (negate values in Python); pop the top two each round, push back the difference if nonzero
  • Cost: O(n log n) time, O(n) space
  • Trap: forgetting Python's heapq is a min-heap — negate on the way in and negate again on the way out

Interview follow-ups

  • What if you smash the two *lightest* stones together instead?

    Swap the max-heap for a min-heap (no negation trick needed in Python, since heapq is already a min-heap) and the same logic works unchanged — pop the two smallest, push back their difference if it's nonzero. The complexity stays O(n log n).

  • The stones keep arriving one at a time, and at any point someone might ask for the current answer if smashing stopped right now. How would you support that efficiently?

    Keep a single running max-heap that every new stone gets pushed into as it arrives, rather than rebuilding one from scratch each time. Since a fresh arrival could be one of the two heaviest, you'd need to redo one round of smashing after every insert to keep the "if we stopped now" answer correct — each insert plus a possible smash stays O(log n), instead of paying O(n log n) to rebuild and re-simulate from zero.

Frequently asked questions

Java's PriorityQueue defaults to a min-heap too, but it accepts a comparator — passing Collections.reverseOrder() flips it into a max-heap directly. C++'s std::priority_queue is a max-heap by default, so no trick is needed there at all. Python's heapq module only ever implements a min-heap with no comparator option, which is why negating the values is the standard workaround.

Not for correctness or for passing this specific problem — with at most 30 stones, even the brute-force approach finishes instantly. It matters for the conversation, though: interviewers use the small constraint to see whether you reach for the right tool (a heap) out of habit, not because you were forced to by the input size. The same shape shows up elsewhere with thousands or millions of items, where the difference between O(n² log n) and O(n log n) is very real.

Yes, when the weights are known to be small and bounded — bucket sort (counting how many stones exist at each weight, in an array indexed by weight) processes everything in O(n + w) time, where w is the largest possible weight, beating O(n log n) when w is small. It's a fair bit more fiddly to implement correctly, and only pays off with that bound on the weights, so the heap is the version worth knowing cold.

The same shape shows up when consolidating work: repeatedly merging the two largest pending batches in a job queue to reduce overhead, or repeatedly combining the two biggest remaining chunks of a partitioned dataset until one is left. A max-heap is the natural structure any time "always grab the current largest" needs to happen more than once.