Last Stone Weight
You're given an array stones of positive weights. Repeatedly take the two heaviest stones and smash them together. If they weigh the same, both are destroyed; otherwise the lighter one is destroyed and the heavier one's weight drops by the lighter one's weight. Stop when at most one stone remains, and return its weight, or 0 if none remain.
Examples
stones = [3,7,2,7] returns 1
The two 7s destroy each other. Then 3 and 2 leave a stone of weight 1, which is the last one.
stones = [10,4] returns 6
Smashing 10 against 4 leaves one stone of weight 6.
stones = [5,5] returns 0
Equal stones destroy each other, leaving nothing.
Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
Hints
Every round you need the two largest values, and then the set of values changes. Which structure keeps the largest value cheap to find after inserts?
Use a max-heap. In Python, push negated weights onto heapq.
While the heap holds two or more stones, pop the top two and push back their difference if it is positive. Return the remaining stone, or 0.
Drill This: Your Approach First
Approach
Each round needs the two largest values and may add one new value, which is exactly what a max-heap supports. Load every stone, then pop the two heaviest; if they differ, push their difference back. Stop when one or zero stones remain. Python's heapq is a min-heap, so store negated weights. Each round is O(log n) and there are at most n rounds: O(n log n) time, O(n) space.
Time
O(n log n)
Space
O(n)
Pitfall
Solutions
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) heap.offer(s);
while (heap.size() > 1) {
int a = heap.poll();
int b = heap.poll();
if (a != b) heap.offer(a - b);
}
return heap.isEmpty() ? 0 : heap.peek();
}
}import heapq
class Solution:
def lastStoneWeight(self, stones) -> int:
heap = [-s for s in stones]
heapq.heapify(heap)
while len(heap) > 1:
a = -heapq.heappop(heap)
b = -heapq.heappop(heap)
if a != b:
heapq.heappush(heap, -(a - b))
return -heap[0] if heap else 0