Domain 1EasyCORE

Last Stone Weight

We are given a collection of stones, each with a positive integer weight. The task is to repeatedly choose the two heaviest stones and smash them together. If the weights of the two stones are equal, both stones are destroyed. If they are not equal, the lighter stone is destroyed, and the heavier stone's weight is reduced by the weight of the lighter stone. This process continues until there is at most one stone left. We need to return the weight of this remaining stone or 0 if no stones remain.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Heap#Greedy

1046. Last Stone Weight

Model: qwen2.5-coder:14b
Topics: Heap,Greedy
FAANG asked: 1
Acceptance rate: 62.4%


The proposed solution is correct and efficient. Here’s the same content with minor improvements for clarity and completeness:

Problem Breakdown

We are given a collection of stones, each with a positive integer weight. The task is to repeatedly choose the two heaviest stones and smash them together. If the weights of the two stones are equal, both stones are destroyed. If they are not equal, the lighter stone is destroyed, and the heavier stone’s weight is reduced by the weight of the lighter stone. This process continues until there is at most one stone left. We need to return the weight of this remaining stone or 0 if no stones remain.

Inputs:

  • An array of integers representing the weights of the stones.

Outputs:

  • A single integer representing the weight of the last remaining stone, or 0 if all stones are destroyed.

Implicit Constraints/Edge Cases:

  • The input list can be empty (return 0).
  • All stone weights are positive integers.
  • The number of stones is between 1 and 30.
  • Stone weights range from 1 to 1000.

Intuition

The brute-force approach would involve repeatedly sorting the array to find the two heaviest stones, which would result in a time complexity of O(n^2 log n) due to the repeated sorting operations. This is inefficient given the constraints.

A better approach involves using a max-heap (priority queue) to efficiently retrieve and manage the two heaviest stones. By negating the stone weights when adding them to the heap, we can use Python’s heapq module, which implements a min-heap by default. This allows us to simulate a max-heap behavior.

Approach

  1. Initialize a Max-Heap:

    • Convert all stone weights to their negative values and push them into a min-heap using heapq.heappush().
  2. Simulate the Smashing Process:

    • While there is more than one stone in the heap:
      • Pop the two largest stones (smallest negative values) from the heap.
      • If they are not equal, push the difference back into the heap as a new stone.
  3. Return the Result:

    • If the heap is empty, return 0.
    • Otherwise, return the weight of the last remaining stone by negating the value at the top of the heap.

Complexity Analysis

  • Time Complexity: O(n log n)

    • Building the heap takes O(n log n).
    • Each extraction and insertion operation in the heap is O(log n), and we perform these operations at most n times.
  • Space Complexity: O(n)

    • We store all stones in the heap, which requires O(n) space.

Solution

import heapq

def lastStoneWeight(stones):
    # Convert all stone weights to negative to simulate a max-heap using min-heap
    max_heap = [-stone for stone in stones]
    heapq.heapify(max_heap)
    
    while len(max_heap) > 1:
        # Pop the two largest stones (smallest negative values)
        y = -heapq.heappop(max_heap)
        x = -heapq.heappop(max_heap)
        
        if x != y:
            # Push the difference back into the heap
            heapq.heappush(max_heap, -(y - x))
    
    # If the heap is empty, return 0; otherwise, return the last remaining stone's weight
    return -max_heap[0] if max_heap else 0

Edge Cases Handled

  • Empty Input: The function returns 0 immediately if the input list is empty.
  • Single Stone: If there is only one stone, it is returned as the result.
  • All Stones Equal Weight: When all stones have the same weight, they will eventually be destroyed, resulting in a final weight of 0.
  • Two Different Weights: The function correctly handles cases where there are two different weights by repeatedly smashing them until one remains.