Last Stone Weight

Difficulty: Easy Source: NeetCode

Problem

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the two heaviest stones and smash them together. Suppose the two heaviest stones have weights x and y where x <= y. The result of this smash is:

• If x == y, both stones are destroyed.
• If x != y, the stone of weight x is destroyed and the stone of weight y has new weight y - x.

Return the weight of the last remaining stone. If there are no stones left, return 0.

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

Example 2: Input: stones = [1] Output: 1

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Heaps / Priority Queues — extracting the maximum element efficiently
• Python’s heapq module — Python only gives you a min-heap; negate values to simulate a max-heap

1. Brute Force

Intuition

Sort the stones on every iteration, grab the two largest, smash them, put the remainder back, and repeat. Sorting every round guarantees we always pick the two heaviest, but it repeats work we’ve already done.

Algorithm

1. While len(stones) > 1: a. Sort stones in descending order. b. Let y = stones[0], x = stones[1]. Remove both. c. If y != x, append y - x back to stones.
2. Return stones[0] if the list is non-empty, else 0.

Solution

def lastStoneWeight(stones):
    stones = stones[:]
    while len(stones) > 1:
        stones.sort(reverse=True)
        y, x = stones[0], stones[1]
        stones = stones[2:]
        if y != x:
            stones.append(y - x)
    return stones[0] if stones else 0


print(lastStoneWeight([2, 7, 4, 1, 8, 1]))  # 1
print(lastStoneWeight([1]))                  # 1
print(lastStoneWeight([2, 2]))               # 0

Complexity

• Time: O(n² log n) — up to n rounds, each with an O(n log n) sort
• Space: O(1) extra (ignoring the copy)

2. Max-Heap

Intuition

We only ever need the two largest elements. A max-heap keeps them at the top and lets us extract them in O(log n) without re-sorting everything. Python’s heapq is a min-heap, so we store negated values — the most negative number is the largest stone.

Algorithm

1. Negate all stone weights and build a heap with heapq.heapify.
2. While more than one stone remains: a. Pop the two largest (most negative values), negate back to get y >= x. b. If y != x, push -(y - x) back onto the heap.
3. Return -heap[0] if the heap is non-empty, else 0.

Solution

import heapq

def lastStoneWeight(stones):
    # Negate to turn min-heap into max-heap
    heap = [-s for s in stones]
    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


print(lastStoneWeight([2, 7, 4, 1, 8, 1]))  # 1
print(lastStoneWeight([1]))                  # 1
print(lastStoneWeight([2, 2]))               # 0

Complexity

• Time: O(n log n) — at most n-1 smash rounds, each O(log n)
• Space: O(n)

Common Pitfalls

Forgetting to negate for max-heap. heapq always gives you the minimum. If you push raw weights, you’ll keep smashing the two lightest stones instead of the two heaviest.

Returning heap[0] instead of -heap[0]. Values in the heap are negated. Always negate back before returning.

Not handling the empty heap case. If the two heaviest stones cancel out on the last round, the heap will be empty. Return 0 in that case, not heap[0] (which would raise an IndexError).