Practice › Heap & Priority Queue
Last Stone Weight
Easy · Heap & Priority Queue · Asked at Amazon, Google, Microsoft
Each turn, take the two heaviest stones x ≤ y and smash them: if x = y both are destroyed, otherwise the y stone becomes y − x. Continue until at most one stone is left. Print its weight, or 0 if no stone remains.
Input
First line: n. Second line: n space-separated integers.
Output
The weight of the last stone, or 0.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ w[i] ≤ 1000
A max-heap gives the two heaviest stones in O(log n).
Example 1
Input
6 2 7 4 1 8 1
Output
1
Example 2
Input
2 5 5
Output
0
Hints
- You always need the two heaviest stones — a max-heap.
- Pop two; if they differ, push the difference back. Repeat while at least two stones remain.
Approach
Put all stones in a max-heap. While it holds two or more, pop y (heaviest) and x; if y > x, push y − x. When one stone is left print it; when none, print 0. (Python's heapq is a min-heap, so store negated weights.)
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<int> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
}
while (pq.size() > 1) {
int y = pq.top();
pq.pop();
int x = pq.top();
pq.pop();
if (y > x) pq.push(y - x);
}
cout << (pq.empty() ? 0 : pq.top()) << "\n";
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
heap = [-x for x in data[1:]]
heapq.heapify(heap)
while len(heap) > 1:
y = -heapq.heappop(heap)
x = -heapq.heappop(heap)
if y > x:
heapq.heappush(heap, -(y - x))
print(-heap[0] if heap else 0)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; i++) pq.add(sc.nextInt());
while (pq.size() > 1) {
int y = pq.poll(), x = pq.poll();
if (y > x) pq.add(y - x);
}
System.out.println(pq.isEmpty() ? 0 : pq.peek());
}
}