Sponsored
Sponsored
This approach uses a max-heap (priority queue) to efficiently track and retrieve the two heaviest stones. By inserting stones with negative values, we use a min-heap implementation in certain languages to simulate max-heap behavior.
Time Complexity: O(n log n), where n is the number of stones. This accounts for the heap operations.
Space Complexity: O(n), to maintain the heap of stones.
1import heapq
2
3def lastStoneWeight(stones):
4 stones = [-stone for stone in stones]
5 heapq.heapify(stones)
6 while len(stones) > 1:
7 first = heapq.heappop(stones)
8 second = heapq.heappop(stones)
9 if first != second:
10 heapq.heappush(stones, first - second)
11 return -stones[0] if stones else 0In this Python solution, we convert the stone weights into negative numbers to use heapq as a max-heap. We then repeatedly extract the two largest stones, compute their difference, and insert it back if it's non-zero.
This approach uses a multiset or bag (analogous to balanced trees or sorted lists in some languages) to manage dynamically sorted stone weights. This allows for direct access to largest elements and supports efficient inserts/removals without full re-sorting.
Time Complexity: O(n^2), due to insert and remove operations in SortedList being O(log n).
Space Complexity: O(n), for storage within the SortedList.
1
In this Python solution with sortedcontainers.SortedList, continuous access to sorted elements permits simplified removal of the heaviest stones, with sorted inserts enabling efficient management and updates of the list's order.