Vultr DocsLatest Content

Last Stone Weight

Updated on 05 June, 2025
Last Stone Weight header image

Problem Statement

In this problem, you are provided with an array of integers, where each integer represents the weight of a stone. These stones are subject to a specific set of rules in a game. Players repeatedly select the two heaviest stones and smash them together. The outcome of smashing two stones varies depending on their weights:

  • If both stones have the same weight, they both get shattered and are completely removed from the game.
  • If the weights are different, the lighter stone breaks, and the heavier stone's new weight will be the difference between the two stones' weights.

The game proceeds in rounds until either none or just one stone remains. The objective is to determine the weight of this last remaining stone. If all stones get shattered, a resulting weight of zero is returned. The intricacies of the game mechanics require effective manipulation and comparison of the stone weights until the end of rounds.

Examples

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 <= 30
  • 1 <= stones[i] <= 1000

Approach and Intuition

Understanding this problem involves realizing that the game revolves around repeatedly manipulating the largest elements in the array. Here are the clear steps based on the provided examples and constraints:

  1. Initialize the game with the array of stones.
  2. Continually identify the two heaviest stones in the set. This will often involve sorting or maintaining a structure like a max heap for efficient largest element retrieval.
  3. Smash the two heaviest stones:
    • If they are of equal weight, both are removed.
    • If not, replace the heavier stone with the difference of the two weights, and remove the lighter stone.
  4. Repeat the above process until one or no stones remain.
  5. Output the weight of the remaining stone or zero if none remains.

The logic can be efficiently handled using a priority queue or max heap since these data structures efficiently support operations to fetch and remove the maximum elements, suitable for simulating our stone game.

During each turn, the efficiency of retrieving and replacing stones determines the overall time complexity of the solution. Given the constraints that limit the number of stones to 30, even repeated sorting provides a feasible approach, but a max heap is optimal for larger input sizes or similar problems.

The challenges involve correctly simulating the game rules and ensuring that the manipulation of the stones' list or heap after each smash operation is correctly implemented. The edge cases such as having only one stone initially or all stones initially having the same weight must be handled properly to avoid errors in the computation.

Solutions

  • Java
  • Python
java 
class Solution {
    
    public int calculateLastStoneWeight(int[] stones) {
        
        int maximumWeight = stones[0];
        for (int stone : stones) {
            maximumWeight = Math.max(maximumWeight, stone);
        }
        int[] weightCounts = new int[maximumWeight + 1];

        for (int stoneWeight : stones) {
            weightCounts[stoneWeight]++;
        }

        int highestWeight = 0;
        int calcWeight = maximumWeight;
        while (calcWeight > 0) {
            if (weightCounts[calcWeight] == 0) {
                calcWeight--;
            } else if (highestWeight == 0) {
                weightCounts[calcWeight] %= 2;
                if (weightCounts[calcWeight] == 1) {
                    highestWeight = calcWeight;
                }
                calcWeight--;
            } else {
                weightCounts[calcWeight]--;
                if (highestWeight - calcWeight <= calcWeight) {
                    weightCounts[highestWeight - calcWeight]++;
                    highestWeight = 0;
                } else {
                    highestWeight -= calcWeight;
                }
            }
        }
        return highestWeight;
    }
}

The given Java code implements a method to solve the problem of determining the weight of the last stone, assuming the stone weights are input as an array of integers. This is how the algorithm functions:

  • First, determine the heaviest stone available by iterating through the stone weights.
  • Next, create an array weightCounts to track the number of times each weight occurs. This array is initialized based on the heaviest stone, ensuring it can accommodate all possible stone weights.
  • Iterate through the weightCounts, decrementing weights when there are stones to smash, until only one stone remains or all stones are smashed away.
  • To resolve simultaneous stone smashes, the code uses a temporary variable highestWeight to remember any leftover weight from previous operations, allowing it to correctly compute the result of successive stone collisions.

Key highlights include:

  • Efficient handling of weights using a counting array, optimizing the process by directly referring to the weights without re-scanning the entire stone collection.
  • The main loop resolves one stone weight at a time, comparing and adjusting the count of current weight stones, reducing the total number of operations needed for finding the last stone.
  • The algorithm guarantees that at the end of all operations, the content in highestWeight will either be the weight of the last stone or zero if all stones completely destroy each other.

This implementation efficiently supports scenarios with multiple stones having large variations in weight, providing an optimal solution to find the weight of the last stone standing.

python 
class Solution:
    def finalStoneWeight(self, stones: List[int]) -> int:
        
        # Initialize a bucket list based on the largest stone weight.
        upper_limit = max(stones)
        bucket = [0] * (upper_limit + 1)

        # Use bucket sort to count stone weights.
        for stone in stones:
            bucket[stone] += 1

        # Determine the final stone weight.
        heaviest = 0
        current = upper_limit
        while current > 0:
            if bucket[current] == 0:
                current -= 1
            elif heaviest == 0:
                bucket[current] %= 2
                if bucket[current] == 1:
                    heaviest = current
                current -= 1
            else:
                bucket[current] -= 1
                if heaviest - current <= current:
                    bucket[heaviest - current] += 1
                    heaviest = 0
                else:
                    heaviest -= current
        return heaviest

The solution to the "Last Stone Weight" problem is implemented in Python using a strategy based on the bucket sort technique for efficiency. Follow the detailed code explanation to understand the approach:

  • Initialize a list called bucket to keep a count of each stone's weight. The size of the bucket is determined by the maximum weight of the stones, ensuring every possible weight from 0 to this maximum is accounted for.

  • Populate the bucket by iterating through the list of stones, incrementing the count at the index corresponding to the stone's weight.

  • To determine the final stone's weight, initiate a variable heaviest to keep track of the heaviest remaining stone that hasn't been smashed yet. Starting from the heaviest possible stone, decrement the weight and adjust the counts in the bucket based on the simulation of the stone-smashing rules.

  • For each distinct weight, if there is an odd count of stones, one stone remains unpaired and becomes the new heaviest. If there is a paired encounter of stones, simulate the collision and update the bucket accordingly, either reducing the heavier stone's count or adjusting the count of the new weight difference.

  • Continue this process until all stones have been addressed, and return the weight of the last remaining stone, if any.

This method relies on the bucket sort concept, significantly optimizing the process by eliminating the need for repeated full list traversals and sorts, thus ensuring that the solution is efficient even for large inputs.

Comments

No comments yet.