Last Stone Weight
Last Stone Weight: Problem Explanation and Solution
The Last Stone Weight problem is a simulation exercise that involves repeatedly smashing the two heaviest stones until no more than one stone remains.
The goal is to determine the weight of the last stone or return 0 if all stones are destroyed.
Problem:
You are given an array of integers stones where stones[i] represents the weight of the ith stone.
We want to run a simulation on the stones as follows:
- At each step we choose the two heaviest stones, with weight
xandyand smash them togethers - If
x == y, both stones are destroyed - If
x < y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
Continue the simulation until there is no more than one stone remaining.
Return the weight of the last remaining stone or return 0 if none remain.
- Recommended Time & Space Complexity
You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.
Problem Breakdown
Key Rules
At each step, select the two heaviest stones:
- If their weights are equal, both are destroyed.
- If their weights are unequal, the heavier stone is reduced by the weight of the lighter one, and the lighter one is destroyed.
Continue until only one stone remains (or none).
Return the weight of the remaining stone or
0if no stones are left.
Example 1
Input: stones = [2,3,6,2,4]
Output: 1
Explanation:
- We smash 6 and 4 and are left with a 2, so the array becomes [2,3,2,2].
- We smash 3 and 2 and are left with a 1, so the array becomes [1,2,2].
- We smash 2 and 2, so the array becomes [1].
Example 2
Input: stones = [1,2]
Output: 1
Constraints:
- 1 <= stones.length <= 20
- 1 <= stones[i] <= 100
Approach
Key Idea: Max-Heap Simulation
To efficiently retrieve the two heaviest stones, we use a max-heap. However, Python’s heapq library provides a min-heap implementation by default, so we simulate a max-heap by storing negative values.
Algorithm
Steps
- Initialize the Heap: Convert all stone weights to negative and push them into a heap.
- Simulation Loop:
- Pop the two largest elements (smallest in the min-heap due to negative values).
- If the stones are not equal, compute the new weight and push it back into the heap.
- Result:
- If the heap is empty, return
0. - Otherwise, return the absolute value of the remaining stone.
- If the heap is empty, return
Hint 1
A naive solution would involve simulating the process by sorting the array at each step and processing the top 2 heaviest stones, resulting in an O(n * nlogn) time complexity. Can you think of a better way? Consider using a data structure that efficiently supports insertion and removal of elements and maintain the sorted order.
Hint 2
We can use a Max-Heap, which allows us to retrieve the maximum element in O(1) time. We initially insert all the weights into the Max-Heap, which takes O(logn) time per insertion. We then simulate the process until only one or no element remains in the Max-Heap. At each step, we pop two elements from the Max-Heap which takes O(logn) time. If they are equal, we do not insert anything back into the heap and continue. Otherwise, we insert the difference of the two elements back into the heap.
There are mainly Four approach to solve this problem –
- Sorting
- Binary Search
- Heap
- Bucket Sort
1. Sorting
- Time complexity: O(n^2logn)
- Space complexity: O(1) or O(n)depending on the sorting algorithm.
Python
C++
Java
JavaScript
Python
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
while len(stones) > 1:
stones.sort()
cur = stones.pop() - stones.pop()
if cur:
stones.append(cur)
return stones[0] if stones else 0C++
class Solution {
public:
int lastStoneWeight(vector& stones) {
while (stones.size() > 1) {
sort(stones.begin(), stones.end());
int cur = stones.back() - stones[stones.size() - 2];
stones.pop_back();
stones.pop_back();
if (cur != 0) {
stones.push_back(cur);
}
}
return stones.empty() ? 0 : stones[0];
}
}; Java
public class Solution {
public int lastStoneWeight(int[] stones) {
List stoneList = new ArrayList<>();
for (int stone : stones) {
stoneList.add(stone);
}
while (stoneList.size() > 1) {
Collections.sort(stoneList);
int cur = stoneList.remove(stoneList.size() - 1) -
stoneList.remove(stoneList.size() - 1);
if (cur != 0) {
stoneList.add(cur);
}
}
return stoneList.isEmpty() ? 0 : stoneList.get(0);
}
} JavaScript
class Solution {
/**
* @param {number[]} stones
* @return {number}
*/
lastStoneWeight(stones) {
while (stones.length > 1) {
stones.sort((a, b) => a - b);
let cur = stones.pop() - stones.pop();
if (cur) {
stones.push(cur);
}
}
return stones.length ? stones[0] : 0;
}
}2. Binary Search
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: or O(n) depending on the sorting algorithm.
Python
Java
C++
JavaScript
Python
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
n = len(stones)
while n > 1:
cur = stones.pop() - stones.pop()
n -= 2
if cur > 0:
l, r = 0, n
while l < r:
mid = (l + r) // 2
if stones[mid] < cur:
l = mid + 1
else:
r = mid
pos = l
n += 1
stones.append(0)
for i in range(n - 1, pos, -1):
stones[i] = stones[i - 1]
stones[pos] = cur
return stones[0] if n > 0 else 0Java
public class Solution {
public int lastStoneWeight(int[] stones) {
Arrays.sort(stones);
int n = stones.length;
while (n > 1) {
int cur = stones[n - 1] - stones[n - 2];
n -= 2;
if (cur > 0) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (stones[mid] < cur) {
l = mid + 1;
} else {
r = mid;
}
}
int pos = l;
n++;
stones = Arrays.copyOf(stones, n);
for (int i = n - 1; i > pos; i--) {
stones[i] = stones[i - 1];
}
stones[pos] = cur;
}
}
return n > 0 ? stones[0] : 0;
}
}
C++
class Solution {
public:
int lastStoneWeight(vector& stones) {
sort(stones.begin(), stones.end());
int n = stones.size();
while (n > 1) {
int cur = stones[n - 1] - stones[n - 2];
n -= 2;
if (cur > 0) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (stones[mid] < cur) {
l = mid + 1;
} else {
r = mid;
}
}
int pos = l;
stones.push_back(0);
for (int i = n + 1; i > pos; i--) {
stones[i] = stones[i - 1];
}
stones[pos] = cur;
n++;
}
}
return n > 0 ? stones[0] : 0;
}
}; JavaScript
/**
* const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
*/
class KthLargest {
/**
* @param {number} k
* @param {number[]} nums
*/
constructor(k, nums) {
this.minHeap = new MinPriorityQueue();
this.k = k;
for (const num of nums) {
this.minHeap.enqueue(num);
}
while (this.minHeap.size() > k) {
this.minHeap.dequeue();
}
}
/**
* @param {number} val
* @return {number}
*/
add(val) {
this.minHeap.enqueue(val);
if (this.minHeap.size() > this.k) {
this.minHeap.dequeue();
}
return this.minHeap.front();
}
}Where m is the number of calls made to add().
2. Binary Search
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: or O(n) depending on the sorting algorithm.
Python
Java
C++
JavaScript
Python
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
n = len(stones)
while n > 1:
cur = stones.pop() - stones.pop()
n -= 2
if cur > 0:
l, r = 0, n
while l < r:
mid = (l + r) // 2
if stones[mid] < cur:
l = mid + 1
else:
r = mid
pos = l
n += 1
stones.append(0)
for i in range(n - 1, pos, -1):
stones[i] = stones[i - 1]
stones[pos] = cur
return stones[0] if n > 0 else 0Java
public class Solution {
public int lastStoneWeight(int[] stones) {
Arrays.sort(stones);
int n = stones.length;
while (n > 1) {
int cur = stones[n - 1] - stones[n - 2];
n -= 2;
if (cur > 0) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (stones[mid] < cur) {
l = mid + 1;
} else {
r = mid;
}
}
int pos = l;
n++;
stones = Arrays.copyOf(stones, n);
for (int i = n - 1; i > pos; i--) {
stones[i] = stones[i - 1];
}
stones[pos] = cur;
}
}
return n > 0 ? stones[0] : 0;
}
}
C++
class Solution {
public:
int lastStoneWeight(vector& stones) {
sort(stones.begin(), stones.end());
int n = stones.size();
while (n > 1) {
int cur = stones[n - 1] - stones[n - 2];
n -= 2;
if (cur > 0) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (stones[mid] < cur) {
l = mid + 1;
} else {
r = mid;
}
}
int pos = l;
stones.push_back(0);
for (int i = n + 1; i > pos; i--) {
stones[i] = stones[i - 1];
}
stones[pos] = cur;
n++;
}
}
return n > 0 ? stones[0] : 0;
}
}; JavaScript
/**
* const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
*/
class KthLargest {
/**
* @param {number} k
* @param {number[]} nums
*/
constructor(k, nums) {
this.minHeap = new MinPriorityQueue();
this.k = k;
for (const num of nums) {
this.minHeap.enqueue(num);
}
while (this.minHeap.size() > k) {
this.minHeap.dequeue();
}
}
/**
* @param {number} val
* @return {number}
*/
add(val) {
this.minHeap.enqueue(val);
if (this.minHeap.size() > this.k) {
this.minHeap.dequeue();
}
return this.minHeap.front();
}
}3. Heap
Time & Space Complexity
- Time complexity: O(nlogn)
- Space complexity: or O(n) depending on the sorting algorithm.
Python
Java
C++
JavaScript
Python
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-s for s in stones]
heapq.heapify(stones)
while len(stones) > 1:
first = heapq.heappop(stones)
second = heapq.heappop(stones)
if second > first:
heapq.heappush(stones, first - second)
stones.append(0)
return abs(stones[0])Java
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue minHeap = new PriorityQueue<>();
for (int s : stones) {
minHeap.offer(-s);
}
while (minHeap.size() > 1) {
int first = minHeap.poll();
int second = minHeap.poll();
if (second > first) {
minHeap.offer(first - second);
}
}
minHeap.offer(0);
return Math.abs(minHeap.peek());
}
} C++
class Solution {
public:
int lastStoneWeight(vector& stones) {
priority_queue maxHeap;
for (int s : stones) {
maxHeap.push(s);
}
while (maxHeap.size() > 1) {
int first = maxHeap.top();
maxHeap.pop();
int second = maxHeap.top();
maxHeap.pop();
if (second < first) {
maxHeap.push(first - second);
}
}
maxHeap.push(0);
return maxHeap.top();
}
}; JavaScript
/**
* const { MaxPriorityQueue } = require('@datastructures-js/priority-queue');
*/
class Solution {
/**
* @param {number[]} stones
* @return {number}
*/
lastStoneWeight(stones) {
const maxPQ = new MaxPriorityQueue();
for (const stone of stones) {
maxPQ.enqueue(stone);
}
while (maxPQ.size() > 1) {
const stone1 = maxPQ.dequeue();
const stone2 = maxPQ.dequeue();
if (stone1 !== stone2) {
maxPQ.enqueue(stone1 - stone2);
}
}
return maxPQ.size() === 1 ? maxPQ.dequeue() : 0;
}
}4. Bucket Sort
Time & Space Complexity
- Time complexity: O(n+w)
- Space complexity: O(w)
Python
Java
C++
JavaScript
Python
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
maxStone = max(stones)
bucket = [0] * (maxStone + 1)
for stone in stones:
bucket[stone] += 1
first = second = maxStone
while first > 0:
if bucket[first] % 2 == 0:
first -= 1
continue
j = min(first - 1, second)
while j > 0 and bucket[j] == 0:
j -= 1
if j == 0:
return first
second = j
bucket[first] -= 1
bucket[second] -= 1
bucket[first - second] += 1
first = max(first - second, second)
return firstJava
public class Solution {
public int lastStoneWeight(int[] stones) {
int maxStone = 0;
for (int stone : stones) {
maxStone = Math.max(maxStone, stone);
}
int[] bucket = new int[maxStone + 1];
for (int stone : stones) {
bucket[stone]++;
}
int first = maxStone, second = maxStone;
while (first > 0) {
if (bucket[first] % 2 == 0) {
first--;
continue;
}
int j = Math.min(first - 1, second);
while (j > 0 && bucket[j] == 0) {
j--;
}
if (j == 0) {
return first;
}
second = j;
bucket[first]--;
bucket[second]--;
bucket[first - second]++;
first = Math.max(first - second, second);
}
return first;
}
}C++
class Solution {
public:
int lastStoneWeight(vector& stones) {
int maxStone = 0;
for (int stone : stones) {
maxStone = max(maxStone, stone);
}
vector bucket(maxStone + 1, 0);
for (int stone : stones) {
bucket[stone]++;
}
int first = maxStone, second = maxStone;
while (first > 0) {
if (bucket[first] % 2 == 0) {
first--;
continue;
}
int j = min(first - 1, second);
while (j > 0 && bucket[j] == 0) {
j--;
}
if (j == 0) {
return first;
}
second = j;
bucket[first]--;
bucket[second]--;
bucket[first - second]++;
first = max(first - second, second);
}
return first;
}
}; JavaScript
class Solution {
/**
* @param {number[]} stones
* @return {number}
*/
lastStoneWeight(stones) {
let maxStone = 0;
for (let stone of stones) {
maxStone = Math.max(maxStone, stone);
}
let bucket = Array(maxStone + 1).fill(0);
for (let stone of stones) {
bucket[stone]++;
}
let first = maxStone, second = maxStone;
while (first > 0) {
if (bucket[first] % 2 === 0) {
first--;
continue;
}
let j = Math.min(first - 1, second);
while (j > 0 && bucket[j] === 0) {
j--;
}
if (j === 0) {
return first;
}
second = j;
bucket[first]--;
bucket[second]--;
bucket[first - second]++;
first = Math.max(first - second, second);
}
return first;
}
}
