Start learning free

LESSON 293 OF 348 · HEAP

Last Stone Weight in TypeScript: Smashing Stones with a Max Heap

Practice O(n log n) Read the full explanation

We have a collection of stones, where each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

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

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

STEP 1 OF 8

Guided

Ctrl + Enter to check

TYPESCRIPT · HEAP

Last Stone Weight in TypeScript, explained

Problem overview

The method lastStoneWeight receives an array stones of positive integer weights. On each turn you take the two heaviest stones and smash them together:

if they weigh the same, both disappear;
otherwise the lighter one disappears and the heavier one stays, with a new weight equal to the difference.

The process repeats until at most one stone is left. The method returns that stone's weight, or 0 if no stone remains.

For [2, 7, 4, 1, 8, 1] the answer is 1. The stones 8 and 7 leave a 1, so the set is 2, 4, 1, 1, 1. Then 4 and 2 leave 2, giving 2, 1, 1, 1. Then 2 and 1 leave 1, giving 1, 1, 1. Then two 1s destroy each other, and a single 1 remains.

Approach: always know the heaviest stone

Every turn needs the two heaviest stones, and the new stone that comes out of a smash has to be considered again on the next turn. A simple approach re-sorts the array on every turn, which costs O(n log n) per turn and O(n² log n) overall.

A max heap does better. It keeps its largest value at the top: extract removes and returns that value, and insert adds a new one, both in O(log n) time. The lesson provides a ready-to-use MaxHeap class, because TypeScript has no heap built in. It also offers heapify to load a whole array at once and size to count the stones inside.

So the plan is: load all the stones, then repeat "extract the heaviest, extract the next heaviest, and put the difference back if it isn't zero". Each smash removes at least one stone from the heap, so the loop must end.

Step by step

Create the heap in a const named heap. The variable never needs to point at another heap, even though the heap's contents change.
Load the stones with heap.heapify(stones). Afterwards the heaviest stone sits at the top.
Loop while heap.size() >= 2. A smash needs two stones. When the loop ends, at most one stone is left.
Extract the first stone into x. It is the heaviest, and extract removes it from the heap as well as returning it.
Extract the second stone into y. Since x came out first, x >= y.
Insert the leftover. If x !== y, insert x - y. Equal weights destroy both stones, so nothing goes back.
Return 0 if the heap is empty after the loop, because every stone was destroyed.
Otherwise return heap.extract(). With exactly one stone left, extracting it returns its weight.

The solution in TypeScript

class Solution {
    lastStoneWeight(stones: number[]): number {
        const heap = new MaxHeap();
        heap.heapify(stones);
        while (heap.size() >= 2) {
            const x = heap.extract();
            const y = heap.extract();
            if (x !== y) {
                heap.insert(x - y);
            }
        }
        if (heap.size() === 0) {
            return 0;
        }
        return heap.extract();
    }
}

The TypeScript details worth a closer look:

size() is a method here. The heap class exposes it as a function you call, with parentheses. A built-in Set or Map is different: its size is a property. An array uses length. Each type has its own spelling, so check which one you are holding.
const inside the loop. x and y are fresh variables on every iteration, and nothing reassigns them, so const is the right choice.
!== compares numbers without conversion. It is the usual comparison in TypeScript. Both sides are numbers, so there is nothing to convert, but it keeps the habit safe.
Numbers stay exact here. TypeScript numbers are doubles, and subtracting whole numbers gives whole numbers, exactly, as long as the values stay below 2^53.

Complexity

Let n be the number of stones.

Time: O(n log n). Building the heap from the array is at most O(n log n). The loop runs at most n - 1 times, because every smash removes at least one stone from the heap. Each pass does two extracts and at most one insert, each O(log n).

Space: O(n). The heap holds the stones.

Edge cases and common mistakes

One stone. [5] never enters the loop, the heap isn't empty, and the method returns 5.
Two equal stones. [3, 3] destroy each other, and the method returns 0.
Everything cancels. [4, 4, 2, 2] also ends at 0.
The wrong loop condition. Smashing needs two stones, so the loop condition must be size() >= 2. With >= 1, the second extract would have nothing to return.
Inserting 0. Without the x !== y check, a zero-weight stone goes into the heap. Because 0 is the smallest possible weight, it only gets smashed last and doesn't change the answer, but it adds useless work.
Swapping the subtraction. y - x would be negative. The heaviest stone always comes out first, so x - y is the non-negative difference.
Sorting the array once and stopping. The stone that comes back after a smash can land anywhere among the others, which is why a structure that handles insertions, such as a heap, is needed.

Testing

[2, 7, 4, 1, 8, 1] gives 1.
[3, 3] gives 0.
[5] gives 5.
[] gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free