Problem Statement

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

Additional information

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

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

• We combine 2 and 4 to get 2 so the array converts to [2, 1, 1, 1].
• We combine 2 and 1 to get 1 so the array converts to [1, 1, 1].
• We combine 1 and 1 to get 0 so the array converts to [1].
• The value of the last stone is 1.

Example 2:

Input: stones = [1]

Output: 1

Brute Force (Sorting)

Intuition

The most straightforward way to simulate this game is to simply sort the array of stones every single time we need to make a move. By sorting the array in ascending order, we guarantee that the two heaviest stones are always sitting at the very end of the list. We can pop them off, smash them, and if there's a leftover piece, throw it back into the list and start the sorting process all over again.

Algorithm

1. Start a while loop that continues as long as len(stones) > 1.

2. Inside the loop, sort the stones array: stones.sort().

3. Pop the last element (the heaviest stone): y = stones.pop().

4. Pop the new last element (the second heaviest stone): x = stones.pop().

5. If y != x, append the remaining weight back to the array: stones.append(y - x).

6. Once the loop finishes, the array will have either 1 stone or 0 stones left.

7. Return stones[0] if the array is not empty, otherwise return 0.

Python

def last_stone_weight(stones: list[int]) -> int:
    while len(stones) > 1:
        stones.sort()
        y = stones.pop()
        x = stones.pop()
        
        if y != x:
            stones.append(y - x)
            
    return stones[0] if stones else 0

Time & Space Complexity

• Time complexity: O(N^2 log N)

  • Reason: In the worst-case scenario, we smash stones and put a piece back N times (where N is the number of stones). Every single time we do this, we run a sorting algorithm which takes O(N log N) time. Multiplying these gives us O(N^2 log N).

• Space complexity: O(N)

  • Reason: While we are modifying the array in place, Python's built-in sort() method (Timsort) can use up to O(N) auxiliary memory in the worst case.

Max-Heap (Priority Queue) - Optimal

Intuition

The game rules dictate that we always need to find the two heaviest stones in the current collection. If we use a standard array and sort it every single time we smash stones, it will be incredibly slow.

The perfect data structure for repeatedly finding the maximum value is a Max-Heap (Priority Queue). It allows us to retrieve the largest element in O(log n) time and insert new elements in O(log n) time.

There is a small catch in Python: the built-in heapq module only implements a Min-Heap. To get around this, we can simply multiply all our stone weights by -1 before adding them to the heap. For example, 8 becomes -8. Since -8 is smaller than -7, the Min-Heap will pop -8 first, perfectly simulating a Max-Heap!

Algorithm

1. Transform the stones array into a Max-Heap by multiplying every element by -1.
2. Use heapq.heapify() to build the heap in-place.
3. Loop while the heap has more than one element (len(stones) > 1):

• Pop the largest element: y = heapq.heappop(stones). (Remember, this is negative).
• Pop the second largest element: x = heapq.heappop(stones).
• If x and y are not equal, the remaining stone weight is y - x. We push this result back into the heap: heapq.heappush(stones, y - x).
  (Note: Because the numbers are negative, (-8) - (-7) = -1, which correctly represents the new stone of weight 1).

4. If the heap is empty, return 0.
5. If one stone remains, return it (remember to multiply by -1 to make it positive again): return -stones[0].

import heapq

def last_stone_weight(stones: list[int]) -> int:
    # Convert to negative values to simulate a Max-Heap
    for i in range(len(stones)):
        stones[i] *= -1
        
    # Build the heap
    heapq.heapify(stones)
    
    # While there is more than 1 stone left
    while len(stones) > 1:
        y = heapq.heappop(stones) # Heaviest stone (most negative)
        x = heapq.heappop(stones) # Second heaviest
        
        # If they are not equal, push the difference back
        if y != x:
            heapq.heappush(stones, y - x)
            
    # Return the last stone (inverted back to positive) or 0 if empty
    return -stones[0] if stones else 0

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Building the initial heap with heapify takes O(N) time. Then, we pop two elements and potentially push one element back up to N - 1 times. Each push/pop operation on the heap takes O(log N) time. Thus, the loop dominates with O(N log N).

• Space complexity: O(1) or O(N)

• Reason: We are modifying the input array stones in-place, which takes O(1) auxiliary space. However, in strict interview settings, if modifying the input is not allowed, creating a copy would take O(N) space.