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 java.util.PriorityQueue;
2
3public class Solution {
4 public int lastStoneWeight(int[] stones) {
5 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
6 for (int stone : stones) {
7 maxHeap.add(stone);
8 }
9 while (maxHeap.size() > 1) {
10 int first = maxHeap.poll();
11 int second = maxHeap.poll();
12 if (first != second) {
13 maxHeap.add(first - second);
14 }
15 }
16 return maxHeap.isEmpty() ? 0 : maxHeap.poll();
17 }
18}In this Java solution, we use PriorityQueue with a custom comparator to maintain a max-heap. We poll the two largest stones, and their difference is added back if non-zero. The final stone weight is returned, or zero if none 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.
1using System.Collections.Generic;
public class Solution {
public int LastStoneWeight(int[] stones) {
SortedDictionary<int, int> sortedStones = new();
foreach (int stone in stones) {
if (!sortedStones.ContainsKey(stone)) {
sortedStones[stone] = 0;
}
sortedStones[stone]++;
}
while (sortedStones.Count > 1) {
int first = RemoveLast(sortedStones);
int second = RemoveLast(sortedStones);
if (first != second) {
int difference = first - second;
if (!sortedStones.ContainsKey(difference)) {
sortedStones[difference] = 0;
}
sortedStones[difference]++;
}
}
foreach (var kvp in sortedStones) {
return kvp.Key;
}
return 0;
}
private int RemoveLast(SortedDictionary<int, int> sortedStones) {
int last = 0;
foreach (var kvp in sortedStones.Reverse()) {
last = kvp.Key;
if (--sortedStones[last] == 0) {
sortedStones.Remove(last);
}
break;
}
return last;
}
}C# takes advantage of SortedDictionary to keep constant order of stone weights, processing by engaging methods to remove last items effectively. Item-specific numbering helps reduce direct set differences.