Last Stone Weight
You are given an array of integers stones where stones[i] represents the weight of the ith stone.
We want to run a simulation on the stones as follows:
- At each step we choose the two heaviest stones, with weight
xandyand smash them togethers - If
x == y, both stones are destroyed - If
x < y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
Continue the simulation until there is no more than one stone remaining.
Return the weight of the last remaining stone or return 0 if none remain.
Example 1:
Input: stones = [2,3,6,2,4]
Output: 1Explanation:
We smash 6 and 4 and are left with a 2, so the array becomes [2,3,2,2].
We smash 3 and 2 and are left with a 1, so the array becomes [1,2,2].
We smash 2 and 2, so the array becomes [1].
Example 2:
Input: stones = [1,2]
Output: 1Constraints:
1 <= stones.length <= 201 <= stones[i] <= 100
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.
Hint 1
A naive solution would involve simulating the process by sorting the array at each step and processing the top 2 heaviest stones, resulting in an O(n * nlogn) time complexity. Can you think of a better way? Consider using a data structure that efficiently supports insertion and removal of elements and maintain the sorted order.
Hint 2
We can use a Max-Heap, which allows us to retrieve the maximum element in O(1) time. We initially insert all the weights into the Max-Heap, which takes O(logn) time per insertion. We then simulate the process until only one or no element remains in the Max-Heap. At each step, we pop two elements from the Max-Heap which takes O(logn) time. If they are equal, we do not insert anything back into the heap and continue. Otherwise, we insert the difference of the two elements back into the heap.