Last Stone Weight solution and explanation
Google
IBM
9 more videos on this problem
Last Stone Weight - Priority Queue - Leetcode 1046 - PythonNeetCode · 12:38 · 112K views
Last stone weight | Leetcode #1046Techdose · 9:11 · 31K views
Last Stone Weight - Leetcode 1046 - Heaps (Python)Greg Hogg · 7:58 · 13K views
Last Stone Weight (LeetCode 1046) | Full Solution with 3 different methods | Priority QueueNikhil Lohia · 12:18 · 4K views
Leetcode | 1046. Last Stone Weight | Easy | Java SolutionDeveloper Docs · 5:50 · 2K views
Leetcode 1046. Last Stone WeightFraz · 7:19 · 1K views
Leetcode - Last Stone Weight (Python)Timothy H Chang · 4:35 · 892 views
Last Stone Weight - LeetCode 1046 - JavaScriptAlgoJS · 5:48 · 814 views
1046. Last Stone Weight (Leetcode Easy)Programming Live with Larry · 7:42 · 598 views
Last Stone Weight - Leetcode 1046 - PythonTechError · 6:16 · 284 views
The problem
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
Approach overview
Problem Overview: You are given a list of stone weights. Each turn, take the two heaviest stones and smash them together. If they are equal, both are destroyed. If not, the heavier stone becomes y - x. Continue until at most one stone remains, then return its weight. The core challenge is repeatedly finding and updating the two largest values efficiently.
Approach 1: Max-Heap based Simulation (O(n log n) time, O(n) space)
This approach models the process exactly as described using a heap (priority queue). Insert all stone weights into a max-heap so the largest element is always accessible in O(log n). Repeatedly extract the two largest stones, compute their difference, and push the remaining weight back into the heap if it is non-zero. Each smash operation involves two heap removals and possibly one insertion, all O(log n). Since at most n operations occur, the total complexity is O(n log n) with O(n) space for the heap. This approach is clean, efficient, and directly mirrors the problem's rules.
Approach 2: Multi-Set / Bag with Sorting (O(n log n) time, O(1)–O(n) space)
Another option is maintaining the stones in a sorted structure such as a multiset or repeatedly sorting an array. After sorting, the two largest values are at the end. Remove them, compute their difference, and insert the result back while maintaining sorted order. Using balanced tree structures or language-provided multisets keeps insertion and deletion at O(log n). If implemented with repeated sorting, each iteration costs O(n log n), which is less efficient but conceptually simple. The multiset version maintains the same asymptotic complexity as the heap solution but usually has slightly higher constant factors.
Recommended for interviews: The max-heap simulation is the expected solution. Interviewers want to see recognition that repeatedly extracting the largest elements is a priority queue problem. Mentioning a simple sorted-array simulation shows understanding of the mechanics, but implementing the heap-based approach demonstrates stronger command of data structures and produces the cleanest O(n log n) solution.
Approach 1: Approach 1: Max-Heap based Simulation
This approach uses a max-heap (priority queue) to efficiently track and retrieve the two heaviest stones. By inserting stones with negative values, we use a min-heap implementation in certain languages to simulate max-heap behavior.
import heapq
def lastStoneWeight(stones):
stones = [-stone for stone in stones]
heapq.heapify(stones)
while len(stones) > 1:
first = heapq.heappop(stones)
second = heapq.heappop(stones)
if first != second:
heapq.heappush(stones, first - second)
return -stones[0] if stones else 0import java.util.PriorityQueue;
public class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
for (int stone : stones) {
maxHeap.add(stone);
}
while (maxHeap.size() > 1) {
int first = maxHeap.poll();
int second = maxHeap.poll();
if (first != second) {
maxHeap.add(first - second);
}
}
return maxHeap.isEmpty() ? 0 : maxHeap.poll();
}
}#include <vector>
#include <queue>
class Solution {
public:
int lastStoneWeight(std::vector<int>& stones) {
std::priority_queue<int> maxHeap(stones.begin(), stones.end());
while (maxHeap.size() > 1) {
int first = maxHeap.top(); maxHeap.pop();
int second = maxHeap.top(); maxHeap.pop();
if (first != second) {
maxHeap.push(first - second);
}
}
return maxHeap.empty() ? 0 : maxHeap.top();
}
};var lastStoneWeight = function(stones) {
stones.sort((a, b) => a - b);
while (stones.length > 1) {
let stone1 = stones.pop();
let stone2 = stones.pop();
if (stone1 !== stone2) {
stones.push(stone1 - stone2);
stones.sort((a, b) => a - b);
}
}
return stones.length === 0 ? 0 : stones[0];
};#include <stdio.h>
#include <stdlib.h>
int comparator(const void *a, const void *b) {
return (*(int *)b) - (*(int *)a);
}
int lastStoneWeight(int* stones, int stonesSize) {
qsort(stones, stonesSize, sizeof(int), comparator);
while (stonesSize > 1) {
if (stones[0] > stones[1]){
stones[1] = stones[0] - stones[1];
stones[0] = stones[stonesSize-1];
stonesSize--;
} else {
stones[0] = stones[stonesSize-1];
stonesSize -= 2;
}
qsort(stones, stonesSize, sizeof(int), comparator);
}
return stonesSize == 1 ? stones[0] : 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LastStoneWeight(int[] stones) {
PriorityQueue<int, int> maxHeap = new();
foreach (int stone in stones) {
maxHeap.Enqueue(stone, -stone);
}
while (maxHeap.Count > 1) {
int first = maxHeap.Dequeue();
int second = maxHeap.Dequeue();
if (first != second) {
maxHeap.Enqueue(first - second, -(first - second));
}
}
return maxHeap.Count == 0 ? 0 : maxHeap.Dequeue();
}
}In this Python solution, we convert the stone weights into negative numbers to use heapq as a max-heap. We then repeatedly extract the two largest stones, compute their difference, and insert it back if it's non-zero.
Time Complexity: O(n log n), where n is the number of stones. This accounts for the heap operations.
Space Complexity: O(n), to maintain the heap of stones.
Approach 2: Approach 2: Multi-Set/Bag with Sorting
This approach uses a multiset or bag (analogous to balanced trees or sorted lists in some languages) to manage dynamically sorted stone weights. This allows for direct access to largest elements and supports efficient inserts/removals without full re-sorting.
from sortedcontainers import SortedList
def lastStoneWeight(stones):
stones = SortedList(stones)
while len(stones) > 1:
first = stones.pop()
second = stones.pop()
if first != second:
stones.add(first - second)
return stones[0] if stones else 0import java.util.TreeSet;
public class Solution {
public int lastStoneWeight(int[] stones) {
TreeSet<Integer> sortedStones = new TreeSet<>();
for (int stone : stones) {
sortedStones.add(stone);
}
while (sortedStones.size() > 1) {
int first = sortedStones.pollLast();
int second = sortedStones.pollLast();
if (first != second) {
sortedStones.add(first - second);
}
}
return sortedStones.isEmpty() ? 0 : sortedStones.last();
}
}#include <set>
#include <vector>
class Solution {
public:
int lastStoneWeight(std::vector<int>& stones) {
std::multiset<int> sortedStones(stones.begin(), stones.end());
while (sortedStones.size() > 1) {
auto it1 = std::prev(sortedStones.end());
int first = *it1; sortedStones.erase(it1);
auto it2 = std::prev(sortedStones.end());
int second = *it2; sortedStones.erase(it2);
if (first != second) {
sortedStones.insert(first - second);
}
}
return sortedStones.empty() ? 0 : *sortedStones.begin();
}
};var lastStoneWeight = function(stones) {
stones.sort((a, b) => a - b);
stones.sort();
while (stones.length > 1) {
let stone1 = stones.pop();
let stone2 = stones.pop();
if (stone1 !== stone2) {
let newStone = stone1 - stone2;
stones.push(newStone);
stones.sort((a, b) => a - b);
}
}
return stones.length === 0 ? 0 : stones[0];
};#include <stdio.h>
#include <stdlib.h>
int comparator(const void *a, const void *b) {
return (*(int *)b) - (*(int *)a);
}
int lastStoneWeight(int* stones, int stonesSize) {
qsort(stones, stonesSize, sizeof(int), comparator);
while (stonesSize > 1) {
if (stones[0] > stones[1]){
stones[1] = stones[0] - stones[1];
stones[0] = stones[stonesSize-1];
stonesSize--;
} else {
stones[0] = stones[stonesSize-1];
stonesSize -= 2;
}
qsort(stones, stonesSize, sizeof(int), comparator);
}
return stonesSize == 1 ? stones[0] : 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LastStoneWeight(int[] stones) {
SortedDictionary<int, int> sortedStones = new();
foreach (int stone in stones) {
if (!sortedStones.ContainsKey(stone)) {
sortedStones[stone] = 0;
}
sortedStones[stone]++;
}
while (sortedStones.Count > 1) {
int first = RemoveLast(sortedStones);
int second = RemoveLast(sortedStones);
if (first != second) {
int difference = first - second;
if (!sortedStones.ContainsKey(difference)) {
sortedStones[difference] = 0;
}
sortedStones[difference]++;
}
}
foreach (var kvp in sortedStones) {
return kvp.Key;
}
return 0;
}
private int RemoveLast(SortedDictionary<int, int> sortedStones) {
int last = 0;
foreach (var kvp in sortedStones.Reverse()) {
last = kvp.Key;
if (--sortedStones[last] == 0) {
sortedStones.Remove(last);
}
break;
}
return last;
}
}In this Python solution with sortedcontainers.SortedList, continuous access to sorted elements permits simplified removal of the heaviest stones, with sorted inserts enabling efficient management and updates of the list's order.
Time Complexity: O(n^2), due to insert and remove operations in SortedList being O(log n).
Space Complexity: O(n), for storage within the SortedList.
Approach 3: Default Approach
function lastStoneWeight(stones: number[]): number {
const pq = new MaxPriorityQueue<number>();
for (const x of stones) {
pq.enqueue(x);
}
while (pq.size() > 1) {
const y = pq.dequeue();
const x = pq.dequeue();
if (x !== y) {
pq.enqueue(y - x);
}
}
return pq.isEmpty() ? 0 : pq.dequeue();
}func lastStoneWeight(stones []int) int {
q := &hp{stones}
heap.Init(q)
for q.Len() > 1 {
y, x := q.pop(), q.pop()
if x != y {
q.push(y - x)
}
}
if q.Len() > 0 {
return q.IntSlice[0]
}
return 0
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int { return heap.Pop(h).(int) }Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Max-Heap based Simulation | Time Complexity: O(n log n), where n is the number of stones. This accounts for the heap operations. |
| Approach 2: Multi-Set/Bag with Sorting | Time Complexity: O(n^2), due to insert and remove operations in SortedList being O(log n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max-Heap based Simulation | O(n log n) | O(n) | General case; best when you need repeated access to the largest elements |
| Multiset / Sorted Structure | O(n log n) | O(1)–O(n) | When language provides ordered multiset or tree structures |
Frequently asked questions
Is Last Stone Weight easy or hard?
Last Stone Weight is classified as an Easy problem on LeetCode with an acceptance rate around 66%. The main concept is recognizing that repeatedly selecting the largest elements suggests using a heap or priority queue.
How to solve Last Stone Weight in O(n)?
An exact O(n) solution is generally not achievable because the algorithm must repeatedly determine the largest elements. Maintaining that ordering requires a structure such as a heap or balanced tree, which introduces a log n factor. The practical optimal solution remains O(n log n) using a priority queue.
What is the best approach for Last Stone Weight?
The most efficient and widely expected approach uses a max-heap (priority queue). Push all stones into the heap, repeatedly remove the two largest values, and insert their difference if it is non-zero. Each heap operation costs O(log n), so the overall complexity becomes O(n log n) with O(n) extra space.
What data structure is used in Last Stone Weight?
A max-heap (priority queue) is the primary data structure. It allows efficient retrieval of the two largest stones at each step. Alternatives include balanced tree multisets or repeatedly sorting arrays, but heaps provide the cleanest implementation.
What is the time complexity of Last Stone Weight?
Using the optimal max-heap solution, the time complexity is O(n log n). Building the heap takes O(n), and each smash operation performs up to two removals and one insertion, each costing O(log n). Since there can be at most n operations, the total runtime is O(n log n).
Last Stone Weight Python or Java solution approach?
In Python, the solution typically uses the heapq module with negative values to simulate a max-heap. In Java, a PriorityQueue with reverse order comparator acts as a max-heap. Both implementations repeatedly poll the two largest elements and push their difference back if needed.
Is Last Stone Weight asked at Google, Amazon, or Meta?
Problems involving heaps and priority queues frequently appear in interviews at companies like Amazon, Google, and Meta. Last Stone Weight itself or close variations are commonly used to test understanding of heap operations and simulation-based problem solving.