Problem Statement:
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weight x is destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Examples:
Example 1:
Input:stones = [2,7,4,1,8,1]
Output:1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that’s the value of the last stone.
Example 2:
Input:stones = [1]
Output:1
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 1000
Approach
- Put all stones in a max-heap so the heaviest stones are always on top.
- While more than one stone remains:
- Remove the two heaviest stones (
yandx). - If they are not equal, insert the difference (
y - x) back into the heap.
- Remove the two heaviest stones (
- Return the weight of the last stone, or
0if none remain.
Time Complexity:
Time Complexity = O(n * m)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: stones = [2, 7, 4, 1, 8, 1]
State Transitions:
Start Function lastStoneWeight([2, 7, 4, 1, 8, 1]) pq = new MaxPriorityQueue() Enqueue all stones i = 0 → stones[0] = 2 → pq.enqueue(2) → pq = [2] i = 1 → stones[1] = 7 → pq.enqueue(7) → pq = [7, 2] i = 2 → stones[2] = 4 → pq.enqueue(4) → pq = [7, 2, 4] i = 3 → stones[3] = 1 → pq.enqueue(1) → pq = [7, 2, 4, 1] i = 4 → stones[4] = 8 → pq.enqueue(8) → pq = [8, 7, 4, 2, 1] i = 5 → stones[5] = 1 → pq.enqueue(1) → pq = [8, 7, 4, 2, 1, 1] -- Enter while loop (pq.size() > 1) -- Iteration 1: → y = pq.dequeue() -> 8 → x = pq.dequeue() -> 7 → y - x = 1 ( > 0 ) → pq.enqueue(1) pq after enqueue -> [4, 2, 1, 1, 1] Iteration 2: → y = pq.dequeue() -> 4 → x = pq.dequeue() -> 2 → y - x = 2 ( > 0 ) → pq.enqueue(2) pq after enqueue -> [2, 1, 1, 1, 2] (equivalently [2, 2, 1, 1, 1]) Iteration 3: → y = pq.dequeue() -> 2 → x = pq.dequeue() -> 2 → y - x = 0 (== 0) → do NOT enqueue pq after removals -> [1, 1, 1] Iteration 4: → y = pq.dequeue() -> 1 → x = pq.dequeue() -> 1 → y - x = 0 (== 0) → do NOT enqueue pq after removals -> [1] Exit while (pq.size() == 1) Return pq.dequeue() || 0 -> returns 1
Final Output: 1
Explanation: repeatedly smash the two largest stones; after all smashes one stone of weight 1 remains, so the function returns 1.
var lastStoneWeight = function(stones) {
let pq = new MaxPriorityQueue();
for(let i=0; i 1){
let y = pq.dequeue();
let x = pq.dequeue();
if(y-x > 0){
pq.enqueue(y-x);
}
}
return pq.dequeue() || 0;
};
import heapq
def lastStoneWeight(stones):
stones = [-s for s in stones] # max heap by negating
heapq.heapify(stones)
while len(stones) > 1:
y = -heapq.heappop(stones)
x = -heapq.heappop(stones)
if y - x > 0:
heapq.heappush(stones, -(y - x))
return -stones[0] if stones else 0
print(lastStoneWeight([2,7,4,1,8,1]))
import java.util.*;
public class Main {
public static int lastStoneWeight(int[] stones) {
PriorityQueue pq = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) pq.add(s);
while (pq.size() > 1) {
int y = pq.poll();
int x = pq.poll();
if (y - x > 0) {
pq.add(y - x);
}
}
return pq.isEmpty() ? 0 : pq.peek();
}
public static void main(String[] args) {
int[] stones = {2,7,4,1,8,1};
System.out.println(lastStoneWeight(stones));
}
}
int lastStoneWeight(vector& stones) {
priority_queue pq(stones.begin(), stones.end());
while (pq.size() > 1) {
int y = pq.top(); pq.pop();
int x = pq.top(); pq.pop();
if (y - x > 0) {
pq.push(y - x);
}
}
return pq.empty() ? 0 : pq.top();
}
int main() {
vector stones = {2,7,4,1,8,1};
cout << lastStoneWeight(stones) << endl;
return 0;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
int extractMax(int arr[], int *n) {
if (*n == 0) return 0;
int maxVal = arr[0];
arr[0] = arr[*n - 1];
(*n)--;
heapify(arr, *n, 0);
return maxVal;
}
void insertHeap(int arr[], int *n, int val) {
arr[*n] = val;
(*n)++;
for (int i = (*n)/2 - 1; i >= 0; i--) {
heapify(arr, *n, i);
}
}
int lastStoneWeight(int stones[], int size) {
for (int i = size/2 - 1; i >= 0; i--) {
heapify(stones, size, i);
}
while (size > 1) {
int y = extractMax(stones, &size);
int x = extractMax(stones, &size);
if (y - x > 0) {
insertHeap(stones, &size, y - x);
}
}
return size == 0 ? 0 : stones[0];
}
int main() {
int stones[] = {2,7,4,1,8,1};
int size = sizeof(stones) / sizeof(stones[0]);
printf("%d\n", lastStoneWeight(stones, size));
return 0;
}
using System;
using System.Collections.Generic;
class Program {
public static int LastStoneWeight(int[] stones) {
PriorityQueue pq = new PriorityQueue();
foreach (var s in stones) {
pq.Enqueue(s, -s); // negative for max-heap
}
while (pq.Count > 1) {
int y = pq.Dequeue();
int x = pq.Dequeue();
if (y - x > 0) {
pq.Enqueue(y - x, -(y - x));
}
}
return pq.Count == 0 ? 0 : pq.Dequeue();
}
static void Main() {
int[] stones = {2,7,4,1,8,1};
Console.WriteLine(LastStoneWeight(stones));
}
}
