1046. Last Stone Weight Easy

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

Approach

Input: Integer array stones, indicating the weight of each stone.

Output: The weight of the last remaining stone (or return 0 if none).

Method Analysis

• The operational pattern of "taking the maximum value every time" is very suitable for using a Max Heap.
• We can use a Max Heap to reduce the complexity.

Specific Walkthrough

1. Put all stones into the max heap:
   • Python's heapq is a min heap, we can simulate a max heap by negating the elements.
   • In JavaScript, a custom MaxHeap is needed.
2. Loop to execute the smashing process:
   • Every time take out the two heaviest stones y and x from the top of the heap (where y >= x).
   • If they are of different weights, put the difference y - x back into the heap.
   • If they are equal, both stones disappear.
3. Termination Condition:
   • Stop when there is only one stone left or the heap is empty.
   • If there are stones left in the heap, return the weight at the top; otherwise return 0.

Complexity Analysis

• Each extract / insert operation on the heap takes O(log n).
• In total, a maximum of n - 1 smash operations are performed.
• Thus, the total time complexity is: O(n log n)
• The heap holds at most n elements: Space Complexity: O(n)

Implementation

python

import heapq
from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        """
        Idea:
        Python's heapq is a min-heap, we can negate the numbers to simulate a max heap.
        Continuously extract the two largest stones and calculate their difference (if unequal, push difference back).
        Ultimately, whatever remains in the heap is the final stone's weight (if empty, return 0).
        """

        # Negate all stone weights to simulate max heap behavior
        stones = [-s for s in stones]
        heapq.heapify(stones)  # Heapify O(n)

        # Loop until at most 1 stone remains in the heap 
        while len(stones) > 1:
            # Extract the two heaviest stones (notice we negate again for true value)
            y = -heapq.heappop(stones)  # Heaviest
            x = -heapq.heappop(stones)  # Second heaviest

            # If weights are unequal, put the shattered difference weight returning to heap 
            if x != y:
                heapq.heappush(stones, -(y - x))
            
        # Returning weight evaluation depending if stones left else 0 logic default
        return -stones[0] if stones else 0

javascript

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    // Relying upon custom configured MaxHeap logic structure limits defined otherwise
    const heap = new MaxHeap();

    // Insertion putting all target elements onto structurally safe array
    for (const x of stones) heap.insert(x);

    // Iterating smashing two extreme stones evaluating difference dynamically
    while (heap.size() > 1) {
        const y = heap.pop(); // Max element
        const x = heap.pop(); // Following heavily loaded

        const diff = y - x;
        // Remaining values successfully preserved re-pushed upon conditions 
        if (diff > 0) heap.insert(diff);
    }

    // Checking length left retrieving isolated component
    return heap.size() === 1 ? heap.pop() : 0;
};

// Simple MaxHeap utility for reference
class MaxHeap {
  constructor() {
    this.data = [];
  }
  size() { return this.data.length; }
  insert(val) {
    this.data.push(val);
    this._heapifyUp();
  }
  pop() {
    if (this.size() === 0) return null;
    const top = this.data[0];
    const end = this.data.pop();
    if (this.size() > 0) {
      this.data[0] = end;
      this._heapifyDown();
    }
    return top;
  }
  _heapifyUp() {
    let i = this.size() - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.data[p] >= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _heapifyDown() {
    let i = 0;
    const n = this.size();
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let largest = i;
      if (l < n && this.data[l] > this.data[largest]) largest = l;
      if (r < n && this.data[r] > this.data[largest]) largest = r;
      if (largest === i) break;
      [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
      i = largest;
    }
  }
}

Complexity Analysis

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Links

1046. Last Stone Weight (English)

1046. 最后一块石头的重量 (Chinese)