LietCode
Last Stone Weight (Easy)

Last Stone Weight (Easy)

Abhi's photo
Abhi
·

5 min read

You are given an array of integers stones where stones[i] is the weight of the i<sup>th</sup> stone.

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

  • If x == y, both stones are destroyed, and

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

At the end of the game, there is at most one stone left.

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
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.

Example 2:

Input: stones = [1]
Output: 1

1) Explain the problem

You are given an array of integers representing the weights of stones. You repeatedly select the two heaviest stones and smash them together. The rules for smashing are:

  • If the stones have the same weight, both are destroyed.

  • If the stones have different weights, the stone with the smaller weight is destroyed, and the larger stone's weight is reduced by the smaller stone's weight.

The game continues until there is at most one stone left. Your task is to return the weight of the last remaining stone. If no stones are left, return 0.

2) Short easy to remember solution/approach

Use a max heap (priority queue) to always fetch the two heaviest stones efficiently. Smash them according to the rules and repeat until one or no stones are left. Return the weight of the remaining stone or 0 if no stones are left.

3) Solution in JavaScript with code commenting

// Helper function to create a max heap
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    // Insert a new element into the heap
    insert(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    // Remove and return the max element (root) of the heap
    extractMax() {
        if (this.size() === 0) return null;
        if (this.size() === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown();
        return max;
    }

    // Get the size of the heap
    size() {
        return this.heap.length;
    }

    // Internal method to maintain heap property after insertion
    _heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[index] <= this.heap[parentIndex]) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    // Internal method to maintain heap property after extraction
    _heapifyDown() {
        let index = 0;
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let largest = index;

            if (leftChildIndex < this.size() && this.heap[leftChildIndex] > this.heap[largest]) {
                largest = leftChildIndex;
            }
            if (rightChildIndex < this.size() && this.heap[rightChildIndex] > this.heap[largest]) {
                largest = rightChildIndex;
            }
            if (largest === index) break;
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            index = largest;
        }
    }
}

// Function to find the weight of the last remaining stone
function lastStoneWeight(stones) {
    const maxHeap = new MaxHeap();

    // Insert all stones into the max heap
    for (const stone of stones) {
        maxHeap.insert(stone);
    }

    // Smash stones until one or none is left
    while (maxHeap.size() > 1) {
        const stone1 = maxHeap.extractMax();
        const stone2 = maxHeap.extractMax();

        if (stone1 !== stone2) {
            maxHeap.insert(stone1 - stone2);
        }
    }

    // Return the last remaining stone's weight or 0 if no stones are left
    return maxHeap.size() === 0 ? 0 : maxHeap.extractMax();
}

4) Explanation of the solution in an easy-to-understand way

Imagine you have a bunch of stones with different weights. You play a game where you always pick the two heaviest stones and smash them together:

  • If they are the same weight, they both disappear.

  • If they are different weights, the smaller one disappears, and the larger one gets smaller by the weight of the smaller one.

You keep doing this until there's one stone or no stones left. You then return the weight of the last stone or 0 if there are no stones left.

5) Code explanation in pointers

  • Create a max heap (priority queue) to keep track of the heaviest stones efficiently.

  • Insert all stone weights into the max heap.

  • Continuously extract the two heaviest stones from the heap and smash them according to the rules.

  • If there's a difference in weight, put the resulting stone back into the heap.

  • Repeat until only one stone is left or no stones are left.

  • Return the weight of the last remaining stone or 0 if no stones are left.

6) Complexities

  • Time Complexity: O(n log n), where n is the number of stones. This is because inserting and extracting from the heap takes O(log n) time, and we do this for each stone.

  • Space Complexity: O(n), where n is the number of stones. This is due to the space required to store the stones in the heap.

heap