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.
1var lastStoneWeight = function(stones) {
2 stones.sort((a, b) => a - b);
3 while (stones.length > 1) {
4 let stone1 = stones.pop();
5 let stone2 = stones.pop();
6 if (stone1 !== stone2) {
7 stones.push(stone1 - stone2);
8 stones.sort((a, b) => a - b);
9 }
10 }
11 return stones.length === 0 ? 0 : stones[0];
12};This JavaScript solution employs sorting to mimic max-heap behavior by always processing the largest elements in the stones array. Differences are resolved and pushed back until one or no stones remain.
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
This Java solution employs TreeSet for maintaining the order of stones naturally. We utilize pollLast to extract the greatest values and manage differences similarly used within this ordered set structure.