1046. Last Stone Weight - Explanation

Description

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 x and y and smash them togethers
If x == y, both stones are destroyed
If x < y, the stone of weight x is destroyed, and the stone of weight y has new weight y - 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.

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

Topics

Array Heap (Priority Queue)

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.

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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Heap / Priority Queue - Efficiently retrieving and removing the maximum (or minimum) element
Sorting - Sorting arrays to process elements in order
Simulation - Implementing step-by-step processes as described in problem statements

1. Sorting

Intuition

You always need to smash the two heaviest stones together.
A simple way to ensure this is:

Sort the list of stones so the heaviest stones are at the end.
Remove the last two stones (the largest values).
Smash them:
- If they are equal → both disappear.
- If they are different → the difference becomes a new stone.
Insert the new stone (if any) back into the list.
Repeat until at most one stone remains.

Sorting each time is not the most efficient approach, but it is straightforward and easy to implement.

Algorithm

While the number of stones is greater than 1:
- Sort the stones in increasing order.
- Remove the two largest stones:
  - Let a = largest stone
  - Let b = second largest stone
- Compute difference = a - b
- If difference > 0, insert the new stone back into the list.
If the list is empty, return 0
Else return the remaining stone.

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 0

public class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> 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);
    }
}

class Solution {
public:
    int lastStoneWeight(vector<int>& 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];
    }
};

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;
    }
}

public class Solution {
    public int LastStoneWeight(int[] stones) {
        List<int> stoneList = new List<int>(stones);
        while (stoneList.Count > 1) {
            stoneList.Sort();
            int cur = stoneList[stoneList.Count - 1] - stoneList[stoneList.Count - 2];
            stoneList.RemoveAt(stoneList.Count - 1);
            stoneList.RemoveAt(stoneList.Count - 1);
            if (cur != 0) {
                stoneList.Add(cur);
            }
        }

        return stoneList.Count == 0 ? 0 : stoneList[0];
    }
}

func lastStoneWeight(stones []int) int {
    for len(stones) > 1 {
		sort.Ints(stones)
		cur := stones[len(stones)-1] - stones[len(stones)-2]
		stones = stones[:len(stones)-2]
		if cur > 0 {
			stones = append(stones, cur)
		}
	}
	if len(stones) == 0 {
		return 0
	}
	return stones[0]
}

class Solution {
    fun lastStoneWeight(stones: IntArray): Int {
        var stonesList = stones.toMutableList()

        while (stonesList.size > 1) {
            stonesList.sort()
            val cur = stonesList.removeAt(stonesList.size - 1) - stonesList.removeAt(stonesList.size - 1)
            if (cur > 0) {
                stonesList.add(cur)
            }
        }
        return if (stonesList.isEmpty()) 0 else stonesList[0]
    }
}

class Solution {
    func lastStoneWeight(_ stones: [Int]) -> Int {
        var stones = stones

        while stones.count > 1 {
            stones.sort()
            let cur = stones.removeLast() - stones.removeLast()
            if cur > 0 {
                stones.append(cur)
            }
        }

        return stones.isEmpty ? 0 : stones[0]
    }
}

impl Solution {
    pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
        let mut stone_list = stones;

        while stone_list.len() > 1 {
            stone_list.sort_unstable();
            let a = stone_list.pop().unwrap();
            let b = stone_list.pop().unwrap();
            let cur = a - b;
            if cur != 0 {
                stone_list.push(cur);
            }
        }

        if stone_list.is_empty() { 0 } else { stone_list[0] }
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2 \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Binary Search

Intuition

We always smash the two heaviest stones.
If we keep the stones in sorted order, the two heaviest are at the end of the array, so we can pick them easily.

After smashing:

We remove the two heaviest stones.
If they are different, their difference becomes a new stone.
To keep the array sorted, we need to insert this new stone at the correct position.

Instead of scanning linearly to find the position, we use binary search to quickly find where this new stone should go in the sorted list, and then shift elements to insert it there. This keeps the list sorted for the next iteration.

Algorithm

Sort the array of stones in non-decreasing order.
Let n be the current number of stones.
While n > 1:
1. Take the last two stones (the two heaviest).
2. Compute cur = heaviest1 - heaviest2.
3. Decrease n by 2 (since we used two stones).
4. If cur > 0:
  - Use binary search on the first n elements to find the position pos where cur should be inserted to keep the array sorted.
  - Increase n by 1.
  - Shift elements from the end to pos one step to the right.
  - Place cur at index pos.
After the loop:
- If n == 1, return the remaining stone.
- If n == 0, return 0.

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 0

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;
    }
}

class Solution {
public:
    int lastStoneWeight(vector<int>& 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;
    }
};

class Solution {
    /**
     * @param {number[]} stones
     * @return {number}
     */
    lastStoneWeight(stones) {
        stones.sort((a, b) => a - b);
        let n = stones.length;

        while (n > 1) {
            let cur = stones.pop() - stones.pop();
            n -= 2;
            if (cur > 0) {
                let l = 0,
                    r = n;
                while (l < r) {
                    let mid = Math.floor((l + r) / 2);
                    if (stones[mid] < cur) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                let pos = l;
                n++;
                stones.push(0);
                for (let i = n - 1; i > pos; i--) {
                    stones[i] = stones[i - 1];
                }
                stones[pos] = cur;
            }
        }
        return n > 0 ? stones[0] : 0;
    }
}

public class Solution {
    public int LastStoneWeight(int[] stones) {
        Array.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;
                Array.Resize(ref stones, n + 1);
                for (int i = n; i > pos; i--) {
                    stones[i] = stones[i - 1];
                }
                stones[pos] = cur;
                n++;
            }
        }
        return n > 0 ? stones[0] : 0;
    }
}

func lastStoneWeight(stones []int) int {
    sort.Ints(stones)
    n := len(stones)

    for n > 1 {
        cur := stones[n-1] - stones[n-2]
        n -= 2

        if cur > 0 {
            pos := sort.Search(n, func(i int) bool {
                return stones[i] >= cur
            })

            for i := n; i > pos; i-- {
                stones[i] = stones[i-1]
            }
            stones[pos] = cur
            n++
        }
    }

    if n > 0 {
        return stones[0]
    }
    return 0
}

class Solution {
    fun lastStoneWeight(stones: IntArray): Int {
        stones.sort()
        var n = stones.size

        while (n > 1) {
            val cur = stones[n-1] - stones[n-2]
            n -= 2

            if (cur > 0) {
                var l = 0
                var r = n
                while (l < r) {
                    val mid = (l + r) / 2
                    if (stones[mid] < cur) {
                        l = mid + 1
                    } else {
                        r = mid
                    }
                }

                for (i in n downTo l+1) {
                    stones[i] = stones[i-1]
                }
                stones[l] = cur
                n++
            }
        }

        return if (n > 0) stones[0] else 0
    }
}

class Solution {
    func lastStoneWeight(_ stones: [Int]) -> Int {
        var stones = stones.sorted()
        var n = stones.count

        while n > 1 {
            let cur = stones.removeLast() - stones.removeLast()
            n -= 2
            if cur > 0 {
                var l = 0, r = n
                while l < r {
                    let mid = (l + r) / 2
                    if stones[mid] < cur {
                        l = mid + 1
                    } else {
                        r = mid
                    }
                }
                let pos = l
                stones.append(0)
                n += 1
                for i in stride(from: n - 1, to: pos, by: -1) {
                    stones[i] = stones[i - 1]
                }
                stones[pos] = cur
            }
        }

        return n > 0 ? stones[0] : 0
    }
}

impl Solution {
    pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
        let mut stones = stones;
        stones.sort_unstable();
        let mut n = stones.len();

        while n > 1 {
            let cur = stones[n - 1] - stones[n - 2];
            n -= 2;
            if cur > 0 {
                let mut l = 0usize;
                let mut r = n;
                while l < r {
                    let mid = (l + r) / 2;
                    if stones[mid] < cur {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                let pos = l;
                if n < stones.len() {
                    stones[n] = 0;
                } else {
                    stones.push(0);
                }
                n += 1;
                for i in (pos + 1..n).rev() {
                    stones[i] = stones[i - 1];
                }
                stones[pos] = cur;
            }
        }

        if n > 0 { stones[0] } else { 0 }
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Heap

Intuition

We always need to repeatedly remove the two heaviest stones.
A max-heap is perfect for this because it lets us efficiently extract the largest values.

Most languages provide min-heaps, so a common trick is to store negative values.
This makes the smallest (most negative) value represent the largest stone.

Process:

Convert all stones to negative and build a heap.
Repeatedly pop the two smallest (i.e., the two heaviest stones).
Smash them:
- If equal → both are destroyed.
- If different → push the negative of their difference back into the heap.
When one or zero stones remain, return the remaining weight or 0.

Algorithm

Convert every stone weight x into -x and build a min-heap.
While the heap contains more than one stone:
- Pop two values a and b (these represent the two heaviest stones).
- If a != b, compute the remaining stone weight:
  - diff = a - b (still negative)
  - Push diff back into the heap.
After the loop:
- If the heap is empty, return 0.
- Otherwise return the absolute value of the remaining stone.

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])

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> 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());
    }
}

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> 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();
    }
};

/**
 * 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;
    }
}

public class Solution {
    public int LastStoneWeight(int[] stones) {
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
        foreach (int s in stones) {
            minHeap.Enqueue(-s, -s);
        }

        while (minHeap.Count > 1) {
            int first = minHeap.Dequeue();
            int second = minHeap.Dequeue();
            if (second > first) {
                minHeap.Enqueue(first - second, first - second);
            }
        }

        minHeap.Enqueue(0, 0);
        return Math.Abs(minHeap.Peek());
    }
}

func lastStoneWeight(stones []int) int {
    pq := priorityqueue.NewWith(func(a, b interface{}) int {
        return a.(int) - b.(int)
    })

    for _, s := range stones {
        pq.Enqueue(-s)
    }

    for pq.Size() > 1 {
        first, _ := pq.Dequeue()
        second, _ := pq.Dequeue()
        if second.(int) > first.(int) {
            pq.Enqueue(first.(int) - second.(int))
        }
    }

    pq.Enqueue(0)
    result, _ := pq.Dequeue()
    return -result.(int)
}

class Solution {
    fun lastStoneWeight(stones: IntArray): Int {
        val minHeap = PriorityQueue<Int>()
        for (s in stones) {
            minHeap.offer(-s)
        }

        while (minHeap.size > 1) {
            val first = minHeap.poll()
            val second = minHeap.poll()
            if (second > first) {
                minHeap.offer(first - second)
            }
        }

        minHeap.offer(0)
        return Math.abs(minHeap.peek())
    }
}

class Solution {
    func lastStoneWeight(_ stones: [Int]) -> Int {
        var heap = Heap(stones)
        while heap.count > 1 {
            let first = heap.popMax()!
            let second = heap.popMax()!
            if first > second {
                heap.insert(first - second)
            }
        }
        return heap.isEmpty ? 0 : heap.popMax()!
    }
}

impl Solution {
    pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
        let mut heap = BinaryHeap::new();
        for s in stones {
            heap.push(s);
        }

        while heap.len() > 1 {
            let first = heap.pop().unwrap();
            let second = heap.pop().unwrap();
            if first != second {
                heap.push(first - second);
            }
        }

        heap.pop().unwrap_or(0)
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Bucket Sort

Intuition

Since all stone values lie within a limited numeric range, we can avoid sorting or using a heap by using bucket sort / frequency counting.

Instead of tracking every stone individually, we store how many stones exist for each possible weight.

Key ideas:

Let bucket[w] store how many stones of weight w we have.
We repeatedly look for the heaviest available stone.
When smashing stones of weights a and b:
- If a == b, they cancel out.
- If different, the leftover stone a - b gets added back into the bucket.
We continue until only one non-zero weight remains.

This works because bucket operations (increment, decrement, scanning) are efficient when the weight range is manageable.

Algorithm

Find the maximum stone weight.
Create a frequency array bucket of size maxWeight + 1.
Count how many stones of each weight exist.
Start from the heaviest weight and repeat:
- If the count at this weight is even, all stones cancel in pairs.
- If odd, one stone remains; find the next heaviest stone to smash with it.
- Compute the difference and update the bucket.
- Move the pointer to the next heaviest relevant weight.
When only one weight remains with an odd count, return it.
If all stones cancel out, return 0.

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 first

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;
    }
}

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        int maxStone = 0;
        for (int stone : stones) {
            maxStone = max(maxStone, stone);
        }

        vector<int> 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;
    }
};

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;
    }
}

public class Solution {
    public int LastStoneWeight(int[] stones) {
        int maxStone = 0;
        foreach (int stone in stones) {
            maxStone = Math.Max(maxStone, stone);
        }

        int[] bucket = new int[maxStone + 1];
        foreach (int stone in 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;
    }
}

func lastStoneWeight(stones []int) int {
    maxStone := 0
    for _, stone := range stones {
        if stone > maxStone {
            maxStone = stone
        }
    }

    bucket := make([]int, maxStone+1)
    for _, stone := range stones {
        bucket[stone]++
    }

    first, second := maxStone, maxStone
    for first > 0 {
        if bucket[first]%2 == 0 {
            first--
            continue
        }

        j := min(first-1, second)
        for 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
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun lastStoneWeight(stones: IntArray): Int {
        val maxStone = stones.max()!!
        val bucket = IntArray(maxStone + 1)
        for (stone in stones) {
            bucket[stone]++
        }

        var first = maxStone
        var second = maxStone
        while (first > 0) {
            if (bucket[first] % 2 == 0) {
                first--
                continue
            }

            var j = minOf(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 = maxOf(first - second, second)
        }
        return first
    }
}

class Solution {
    func lastStoneWeight(_ stones: [Int]) -> Int {
        guard let maxStone = stones.max() else { return 0 }

        var bucket = [Int](repeating: 0, count: maxStone + 1)
        for stone in stones {
            bucket[stone] += 1
        }

        var first = maxStone
        var second = maxStone

        while first > 0 {
            if bucket[first] % 2 == 0 {
                first -= 1
                continue
            }

            var j = min(first - 1, second)
            while j > 0 && 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 first
    }
}

impl Solution {
    pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
        let max_stone = *stones.iter().max().unwrap() as usize;
        let mut bucket = vec![0i32; max_stone + 1];
        for &stone in &stones {
            bucket[stone as usize] += 1;
        }

        let mut first = max_stone;
        let mut second = max_stone;

        while first > 0 {
            if bucket[first] % 2 == 0 {
                first -= 1;
                continue;
            }

            let mut j = first.min(second).saturating_sub(1);
            while j > 0 && bucket[j] == 0 {
                j -= 1;
            }

            if j == 0 {
                return first as i32;
            }

            second = j;
            bucket[first] -= 1;
            bucket[second] -= 1;
            bucket[first - second] += 1;
            first = (first - second).max(second);
        }

        first as i32
    }
}

Time & Space Complexity

Time complexity: $O(n + w)$
Space complexity: $O(w)$

Where $n$ is the length of the $stones$ array and $w$ is the maximum value in the $stones$ array.

Common Pitfalls

Using a Min-Heap Instead of Max-Heap

Many languages provide min-heaps by default (like Python's heapq). You need to either use a max-heap or negate the values when inserting and extracting. Forgetting this results in smashing the two smallest stones instead of the two heaviest.

Forgetting to Handle the Empty Result Case

After all smashing is complete, the stones array could be empty (all stones canceled out). Returning stones[0] without checking if the array is empty causes an index error. Always check if the result is empty and return 0 in that case.