Last Stone Weight

Problem Description

You are given an array of integers stones where stones[i] is the weight of the i-th 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,
• 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.

Examples

Constraints

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

Max-Heap Stone Smashing Simulation

To repeatedly find and extract the two heaviest stones, we can use a Max-Heap (Priority Queue).

1. Initialize the max-heap with all stone weights.
2. While the heap contains more than 1 stone:
   • Extract the heaviest stone y and the second heaviest stone x.
   • If y > x, push the remaining weight y - x back into the heap.
3. If the heap is empty, return 0. Otherwise, return the remaining stone weight.

Solution 1: Max-Heap Simulation

Use a max-heap to fetch the two heaviest stones on each iteration, updating the heap until at most 1 stone remains.

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Initialize max-heap using reverseOrder comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones) {
            maxHeap.offer(stone);
        }

        while (maxHeap.size() > 1) {
            int y = maxHeap.poll(); // heaviest
            int x = maxHeap.poll(); // second heaviest

            if (y != x) {
                maxHeap.offer(y - x); // push back remainder
            }
        }

        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        # Python heapq is a min-heap, so we negate values to simulate a max-heap
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)
        
        while len(max_heap) > 1:
            y = -heapq.heappop(max_heap)  # heaviest
            x = -heapq.heappop(max_heap)  # second heaviest
            
            if y != x:
                heapq.heappush(max_heap, -(y - x))
                
        return -max_heap[0] if max_heap else 0

#include <vector>
#include <queue>

class Solution {
public:
    int lastStoneWeight(std::vector<int>& stones) {
        std::priority_queue<int> maxHeap(stones.begin(), stones.end());

        while (maxHeap.size() > 1) {
            int y = maxHeap.top(); // heaviest
            maxHeap.pop();
            int x = maxHeap.top(); // second heaviest
            maxHeap.pop();

            if (y != x) {
                maxHeap.push(y - x);
            }
        }

        return maxHeap.empty() ? 0 : maxHeap.top();
    }
};

Complexity Analysis

• Time Complexity: O(n log n) since pushing/popping from the heap takes O(log n) time, and we perform at most n-1 combine steps.
• Space Complexity: O(n) auxiliary space to store elements in the heap.

← All Problems