Last Stone Weight

Difficulty: Easy | Acceptance: 66.50% | Paid: No Topics: Array, Heap (Priority Queue)

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, or 0 if there are no stones left.

• Examples
• Constraints
• Approach 1: Sorting Simulation
• Approach 2: Max Heap (Priority Queue)

Examples

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.

Input: stones = [1,3]
Output: 1

Constraints

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

Approach 1: Sorting Simulation

Intuition Since we always need the two heaviest stones, we can repeatedly sort the array to access the largest elements at the end. After smashing them, we update the array and sort again.

Steps

• Sort the array in ascending order.
• While there is more than one stone:
  • Take the last two elements (y and x).
  • Remove them from the array.
  • If x != y, append (y - x) to the array.
  • Sort the array again.
• Return the remaining stone or 0.

from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while len(stones) > 1:
            stones.sort()
            y = stones.pop()
            x = stones.pop()
            if x != y:
                stones.append(y - x)
        return stones[0] if stones else 0

Complexity

• Time: O(N² log N) — We sort up to N times.
• Space: O(1) or O(N) depending on the sorting algorithm.
• Notes: Simple to implement but inefficient for large inputs.

Approach 2: Max Heap (Priority Queue)

Intuition A Max Heap allows us to efficiently retrieve and remove the largest element in O(log N) time. This is optimal for repeatedly accessing the two heaviest stones.

Steps

• Insert all stones into a Max Heap.
• While the heap has more than one stone:
  • Pop the largest stone (y).
  • Pop the second largest stone (x).
  • If x != y, push (y - x) back into the heap.
• Return the remaining stone or 0.

import heapq
from typing import List

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

Complexity

• Time: O(N log N) — Each heap operation takes O(log N).
• Space: O(N) — To store the heap.
• Notes: The most efficient approach for this problem.