Last Stone Weight

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

With a max-heap, at most n-1 rounds of two pops and one push take O(n log n) time and O(n) space. Sorting the whole pile every round takes O(n² log n) .

EasyHeap

+10

You have a pile of stones, and stones[i] is the weight of stone i. Each round, take the two heaviest stones and smash them together. If they weigh the same, both are destroyed. If not, the lighter one is destroyed and the heavier one shrinks to the difference of the two weights.

Write lastStoneWeight, which plays rounds until at most one stone is left and returns its weight, or 0 when no stone is left.

Function

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: the weights of the stones in the pile
Returnsinteger: the weight of the last stone, or 0 if none is left

Constraints

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Examples

Input: stones = [3, 9, 4, 6, 2]
Output: 0
Explanation: 9 and 6 leave a 3, then 4 and 3 leave a 1, then 3 and 2 leave another 1. The two 1 stones destroy each other, so the answer is 0.

Input: stones = [10, 4, 1]
Output: 5
Explanation: 10 and 4 leave a 6, and 6 and 1 leave a 5. One stone remains, weighing 5.

Input: stones = [8]
Output: 8
Explanation: A single stone has nothing to be smashed against, so its weight 8 is the answer.

Follow-up

The weights are at most 1000. Can you use that bound to finish in O(n + W) time, where W is the largest weight, without a heap?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

There is no formula to skip ahead: you play every round. Each round needs the two heaviest stones of a pile that keeps changing, because a smashed stone can come back lighter. A max-heap hands out the heaviest stone and takes a new one back in O(log n).

Sort the pile every round

Correct, but does not finish on the largest tests

Intuition

Follow the rules literally: sort the pile, take the two heaviest off the end, and put their difference back if it is not zero. Sort again every round, because the difference can land anywhere. In the first example 9 and 6 leave a 3, which belongs below the 4.

Every round removes at least one stone, so there are up to n-1 rounds, each sorting up to n stones: O(n² log n). For n = 10^4 that is about 10^4 sorts of up to 10^4 numbers.

Algorithm

Copy the stones into a list called pile.
While the pile holds more than one stone, sort it in increasing order.
Take off the last two stones, heaviest and second.
If they differ, add heaviest - second back to the pile.
Return the remaining stone, or 0 when the pile is empty.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Max-heap

Intuition

A max-heap keeps the largest value at the top, and removing the top or adding a value costs O(log n). Put every stone in it. Each round, pop twice for the two heaviest and push the difference back if it is not zero; the heap moves it into place. For [10, 4, 1] you pop 10 and 4 and push 6, then pop 6 and 1 and push 5.

There are at most n-1 rounds of two pops and one push, so the time is O(n log n) and the space O(n). In languages without a built-in heap, the solution keeps one in an array, with the parent of index i at (i-1)/2.

Algorithm

Put every stone in a max-heap.
While the heap holds more than one stone, pop the heaviest and then the second heaviest.
If they differ, push heaviest - second.
Return the top of the heap, or 0 when it is empty.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Pitfalls and edge cases

Returning the top of an empty pile. When the last two stones weigh the same, as in the first example, nothing is left and the answer is 0.
Using a min-heap by accident. Python's heapq and Java's default PriorityQueue hand out the smallest value; negate the weights or pass a reverse comparator.
Forgetting the sign with negated weights. Both popped values are negative, so the value to push is -(heaviest - second).
Sorting once at the start and walking the list. The difference can be lighter than stones you have not touched yet, so the order goes stale after the first round.

Frequently asked questions3

What is the time complexity of Last Stone Weight?

With a max-heap, at most n-1 rounds of two pops and one push take O(n log n) time and O(n) space. Sorting the whole pile every round takes O(n² log n).

Why use a heap for Last Stone Weight instead of a sorted list?

A sorted list gives the two heaviest stones at once, but putting the difference back in order shifts up to n entries, O(n²) over all rounds. A heap only answers "what is the largest" and accepts a new value, both in O(log n), which is all the simulation asks for.

Does the order of smashing equal weights change the answer?

No. When several stones share the heaviest weight, the two you pick weigh the same either way, so the pile after the round holds the same weights. The answer depends only on the weights.

def lastStoneWeight(stones):
    # Write code here

Test #1

Test #2

Test #3

Argument

stones = [3, 9, 4, 6, 2]

Expected Output