Problem Description

You have a collection of stones, each with a specific weight given in an array stones. The goal is to play a stone-smashing game until at most one stone remains.

The game works as follows:

• In each turn, select the two heaviest stones
• Smash them together based on these rules:
  • If both stones have equal weight, both are completely destroyed
  • If they have different weights, the lighter stone is destroyed and the heavier stone's weight is reduced by the lighter stone's weight
• Continue playing until you have one or zero stones left

Your task is to determine the weight of the final remaining stone. If no stones remain, return 0.

Example walkthrough: If stones = [2, 7, 4, 1, 8, 1]:

• Pick 8 and 7 → smash them → 8-7=1 remains, array becomes [2, 4, 1, 1, 1]
• Pick 4 and 2 → smash them → 4-2=2 remains, array becomes [2, 1, 1, 1]
• Pick 2 and 1 → smash them → 2-1=1 remains, array becomes [1, 1, 1]
• Pick 1 and 1 → smash them → both destroyed, array becomes [1]
• Only one stone left with weight 1

The solution uses a max heap (priority queue) to efficiently track and retrieve the heaviest stones. Since Python's heapq implements a min heap, the code negates all values to simulate a max heap. It repeatedly extracts the two largest stones, calculates their difference if they're unequal, and pushes the result back into the heap until one or zero stones remain.

Intuition

The key insight is recognizing that we need to repeatedly find and process the two heaviest stones. This immediately suggests using a data structure that can efficiently give us the maximum elements.

Think about it step by step: after each smash, we might have a new stone (the difference) that needs to be placed back among the remaining stones. This new stone could be anywhere in the ordering - it might become the new heaviest, the lightest, or somewhere in between. We need a way to maintain this ordering automatically.

A max heap is perfect for this scenario because:

• We can extract the maximum element in O(log n) time
• We can insert a new element and maintain the heap property in O(log n) time
• The heap automatically keeps track of which stone is currently the heaviest

Since Python's heapq module only provides a min heap, we can cleverly work around this by negating all values. When we insert -x into a min heap, the smallest value (most negative) actually represents our largest original value. For example, if we have stones [2, 7, 4], we store them as [-2, -7, -4] in the min heap. The min heap will give us -7 first (which represents our maximum value 7).

The process continues naturally: pop two stones, calculate their difference if needed, and push the result back. The heap structure ensures we're always working with the current two heaviest stones without having to manually sort or search through the array after each operation. This transforms what could be an O(n²) sorting problem into an O(n log n) heap problem.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a max heap data structure to efficiently manage the stones. Here's how the solution works step by step:

1. Initialize the Max Heap

h = [-x for x in stones]
heapify(h)

Since Python's heapq provides only a min heap, we negate all stone weights to simulate a max heap. The heapify() function transforms the list into a heap structure in O(n) time.

2. Process Stones Until One or None Remain

while len(h) > 1:
    y, x = -heappop(h), -heappop(h)

The main loop continues while we have at least 2 stones. In each iteration:

• Extract the two heaviest stones using heappop() twice
• Negate them back to get the original positive weights
• Store them as y (heaviest) and x (second heaviest)

3. Handle the Smashing Result

if x != y:
    heappush(h, x - y)

After smashing:

• If the stones are equal (x == y), both are destroyed - we don't push anything back
• If they're different, we push the difference back into the heap
• Note: we push x - y (which is negative) to maintain our max heap simulation

4. Return the Final Result

return 0 if not h else -h[0]

After the loop:

• If the heap is empty (not h), all stones were destroyed, return 0
• If one stone remains, return its weight by negating h[0] to get the positive value

Time Complexity: O(n log n) where n is the number of stones. Each heap operation takes O(log n) and we perform at most 2n operations.

Space Complexity: O(n) for storing the heap.

Example Walkthrough

Let's trace through a small example with stones = [4, 3, 6, 2] to see how the max heap approach works:

Initial Setup:

• Original stones: [4, 3, 6, 2]
• Create negated array: [-4, -3, -6, -2]
• After heapify, our min heap looks like: [-6, -3, -4, -2]
  • The smallest (most negative) value -6 represents our largest stone 6

Round 1:

• Pop -6 → stone weight 6 (heaviest)
• Pop -4 → stone weight 4 (second heaviest)
• Smash them: 6 - 4 = 2 remains
• Push -2 back to heap
• Heap after insertion: [-3, -2, -2]

Round 2:

• Pop -3 → stone weight 3 (heaviest)
• Pop -2 → stone weight 2 (second heaviest)
• Smash them: 3 - 2 = 1 remains
• Push -1 back to heap
• Heap after insertion: [-2, -1]

Round 3:

• Pop -2 → stone weight 2 (heaviest)
• Pop -1 → stone weight 1 (second heaviest)
• Smash them: 2 - 1 = 1 remains
• Push -1 back to heap
• Heap after insertion: [-1]

Final Result:

• Only one stone remains in heap: [-1]
• Return the positive value: 1

This walkthrough demonstrates how the negated values in the min heap always give us the two largest stones first, and how the heap automatically maintains the correct ordering after each new stone (difference) is added back.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

• Initial heapification of the list takes O(n) time where n is the number of stones
• The while loop runs at most n-1 times (in the worst case, we reduce the number of stones by 1 in each iteration)
• In each iteration, we perform:
  • Two heappop operations: O(log k) each, where k is the current heap size
  • At most one heappush operation: O(log k)
• Since the heap size decreases from n to 1, the total time for all heap operations is:
  • O(log n) + O(log(n-1)) + ... + O(log 2) = O(n log n)
• Therefore, the overall time complexity is O(n) + O(n log n) = O(n log n)

Space Complexity: O(n)

• We create a new list h that stores all n stones (with negated values), which requires O(n) space
• The heap operations are performed in-place on this list, so no additional space proportional to input size is needed
• Only a constant amount of extra space is used for variables x and y
• Therefore, the space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Negate Values When Using Min Heap as Max Heap

A frequent mistake is inconsistent negation when simulating a max heap with Python's min heap. Developers often forget to negate at one of these critical points:

• When initially converting the array to negative values
• When extracting values from the heap
• When pushing the difference back into the heap
• When returning the final result

Incorrect Implementation:

# Pitfall: Forgetting to negate when pushing back
max_heap = [-stone for stone in stones]
heapq.heapify(max_heap)

while len(max_heap) > 1:
    first = -heapq.heappop(max_heap)
    second = -heapq.heappop(max_heap)
  
    if first != second:
        # WRONG: Pushing positive value into min heap
        heapq.heappush(max_heap, first - second)  # Bug!
      
# WRONG: Forgetting to negate the final result
return 0 if not max_heap else max_heap[0]  # Bug!

Correct Implementation:

max_heap = [-stone for stone in stones]
heapq.heapify(max_heap)

while len(max_heap) > 1:
    first = -heapq.heappop(max_heap)
    second = -heapq.heappop(max_heap)
  
    if first != second:
        # Correct: Push negative of difference
        heapq.heappush(max_heap, -(first - second))
      
# Correct: Negate to get positive weight
return 0 if not max_heap else -max_heap[0]

2. Modifying Original Input Array

Another pitfall is directly modifying the input array instead of creating a copy, which can cause issues if the original data needs to be preserved.

Problematic Approach:

# Directly modifying input - may cause issues
for i in range(len(stones)):
    stones[i] = -stones[i]
heapq.heapify(stones)

Better Approach:

# Create a new list to avoid modifying input
max_heap = [-stone for stone in stones]
heapq.heapify(max_heap)

3. Incorrect Order When Popping Two Stones

Some developers mistakenly assume the order doesn't matter when extracting two stones, but maintaining consistency helps avoid logical errors.

Potentially Confusing:

while len(max_heap) > 1:
    # Mixing up which is first/second can lead to errors
    stone1 = -heapq.heappop(max_heap)
    stone2 = -heapq.heappop(max_heap)
  
    if stone1 < stone2:  # Now need to check which is larger
        heapq.heappush(max_heap, -(stone2 - stone1))
    elif stone1 > stone2:
        heapq.heappush(max_heap, -(stone1 - stone2))

Clear and Consistent:

while len(max_heap) > 1:
    # Always extract in order: first is guaranteed >= second
    first = -heapq.heappop(max_heap)
    second = -heapq.heappop(max_heap)
  
    if first != second:
        # Simple: first - second is always >= 0
        heapq.heappush(max_heap, -(first - second))