Last Stone Weight

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

With a max-heap, building the heap and playing at most n-1 rounds of two pops and one push takes O(n log n) time and O(n) space. Sorting the whole pile every round instead 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 a function named lastStoneWeight that plays rounds until at most one stone is left, and returns the weight of that stone, 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 stones of weight 1 destroy each other, so nothing is left and 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.

+13 hidden tests on Submit

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

The rules are a simulation: there is no formula to skip ahead, so 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. Sorting again every round finds them but costs O(n log n) per round. 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 so the two heaviest stones sit at the end, take them off, and if their weights differ, put the difference back. Repeat until the pile holds one stone or none.

The difference can land anywhere in the order. In the first example, 9 and 6 leave a 3, which belongs below the 4, so you sort again before the next round to find the new two heaviest.

Every round removes at least one stone, so there are up to n-1 rounds, each with a sort of up to n stones: O(n² log n). With n = 10^4 that is about 10^4 sorts of up to 10^4 numbers, at least 5 × 10^7 steps even when the sort notices that the list is almost sorted, and several times that when it does not. That is too slow for the largest tests, while the heap below needs only a few hundred thousand steps.

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

Each round you only ever need the largest stones, never the full order. A max-heap is built for that: it keeps the largest value at the top, and removing the top or adding a value costs O(log n).

Put every stone in the heap. Each round, pop twice to get the two heaviest. If they differ, push the difference back; the heap moves it to its correct place on its own. For [10, 4, 1] you pop 10 and 4 and push 6, then pop 6 and 1 and push 5, and the heap holds only 5.

There are at most n-1 rounds, each with two pops and at most one push, so the time is O(n log n) and the heap uses O(n) space. Some languages ship a heap: Python's heapq is a min-heap, so it stores negated weights; Java has PriorityQueue, C++ priority_queue, Go container/heap, Rust BinaryHeap and PHP SplMaxHeap. In the other languages the solution writes its own heap in an array: the parent of index i is at (i-1)/2, and a new value climbs while it beats its parent.

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

The simulation is short, so the bugs hide in the ends and in the heap itself.

Returning the top of an empty pile. When the last two stones weigh the same, 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 to negate back. With heapq, both popped values are negative, so the difference you push is -(heaviest - second).
Sorting once at the start and walking the list. The difference of two stones can be lighter than stones you have not touched yet, so a fixed order goes stale after the first round.

Frequently asked questions4

What is the time complexity of Last Stone Weight?

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

Why use a heap for Last Stone Weight?

Every round asks for the two largest values of a collection that changes after each round. A heap answers "what is the largest" and accepts a new value in O(log n), without keeping the whole collection sorted. That is exactly the work the simulation repeats.

Can Last Stone Weight be solved without a heap?

Yes, because the weights are small. Count how many stones have each weight from 1 to 1000 and walk down from the heaviest weight. Equal stones cancel in pairs, and a new stone is always lighter than the heaviest one used to make it, so the walk only moves down. That runs in O(n + W) time for the largest weight W.

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, which is why every correct solution returns the same number.

Python

def lastStoneWeight(stones):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected