algoadvance

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

We repeatedly choose the two heaviest stones and smash them together. Suppose the heaviest 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, a new stone of weight y - x is placed in the list of stones.

At the end of the process, there is at most one stone left. Return the weight of this last remaining stone. If there are no stones left, return 0.

Example

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 last remaining stone.

Clarifying Questions

1. Can the input array be empty or contain a single stone?
   • If the array is empty, the function should return 0.
   • If the array contains only one stone, the weight of that stone should be returned.
2. Will the stones’ weights always be positive integers?
   • Yes, stone weights are represented as positive integers.

Strategy

To efficiently determine the two heaviest stones repeatedly:

1. Utilize a max-heap (priority queue) because it allows efficient removal of the largest element.
2. Python’s heapq module implements a min-heap, so we will insert negative weights to simulate a max-heap.

Steps:

1. Insert all the stones into a max-heap (using negative values).
2. Continuously extract the two largest stones (convert to positive by negating).
3. Compute the result of smashing them together and insert the result back into the heap if it’s non-zero.
4. If there is one stone left, return its weight; if no stones are left, return 0.

Code

import heapq

def lastStoneWeight(stones):
    # Convert all stones to negative numbers to use heapq as a max-heap
    max_heap = [-stone for stone in stones]
    heapq.heapify(max_heap)
    
    while len(max_heap) > 1:
        # Extract the two largest stones
        largest = -heapq.heappop(max_heap)
        second_largest = -heapq.heappop(max_heap)
        
        if largest != second_largest:
            # The new stone weight to be added back
            new_stone = largest - second_largest
            # Push the negative of this new stone into the heap
            heapq.heappush(max_heap, -new_stone)
    
    # If no stones are left, return 0. Otherwise, return the weight of the remaining stone.
    return -max_heap[0] if max_heap else 0

Time Complexity

• Heap initialization: O(n)
• Extracting two heaviest stones and inserting their difference: O(log n) per operation
• In the worst-case scenario, we might have to perform n-1 operations where n is the number of stones.

Thus, the overall time complexity is O(n log n).

This solution efficiently manages the repeated extraction and insertion of stones based on their weights using a max-heap simulated by a min-heap with negative values.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?