Algorithm
Problem Name: 1046. Last Stone Weight
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 weightxis 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.
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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int stone : stones) {
pq.add(stone);
}
while (pq.size() > 1) {
int firstStone = pq.poll();
int secondStone = pq.poll();
if (firstStone != secondStone) {
pq.add(firstStone - secondStone);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const lastStoneWeight = function(stones) {
stones.sort((a, b) => a - b)
while (stones.length > 1) {
const num = Math.abs(stones.pop() - stones.pop())
stones.splice(stones.findIndex(item => item >= num), 0, num)
}
return stones[0]
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
for _ in range(len(stones) - 1):
bisect.insort(stones, stones.pop() - stones.pop())
return stones[0]
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _1046_LastStoneWeight
{
public int LastStoneWeight(int[] stones)
{
var counts = new int[1001];
var maxWeight = int.MinValue;
foreach (var stone in stones)
{
counts[stone]++;
maxWeight = Math.Max(maxWeight, stone);
}
var biggestWeight = 0;
var currentWeight = maxWeight;
while (currentWeight > 0)
{
if (counts[currentWeight] == 0)
{
currentWeight--;
continue;
}
if (biggestWeight == 0)
{
counts[currentWeight] %= 2;
if (counts[currentWeight] == 1)
{
biggestWeight = currentWeight;
counts[currentWeight] = 0;
}
currentWeight--;
}
else
{
counts[currentWeight]--;
if (biggestWeight - currentWeight < = currentWeight)
{
counts[biggestWeight - currentWeight]++;
biggestWeight = 0;
}
else
{
biggestWeight -= currentWeight;
}
}
}
return biggestWeight;
}
}
}
Input
Output