Last Stone Weight

How it works

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.

Steps

1. Find the maximum stone weight.
2. Create a frequency array bucket of size maxWeight + 1.
3. Count how many stones of each weight exist.
4. 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.
5. When only one weight remains with an odd count, return it.
6. If all stones cancel out, return 0.

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.

Things to watch for

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.

from typing import List

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

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