1046. Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the $i^{th}$ 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 weight x is destroyed, and the stone of weight y has new weight y - 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 <= 30
• 1 <= stones[i] <= 1000

From: LeetCode
Link: 1046. Last Stone Weight

Solution:

Ideas:

• Repeatedly find the two heaviest stones.
• Smash them:
  • equal: both removed
  • different: keep the difference
• Continue until 0 or 1 stone remains.

Since stones.length <= 30, this simple simulation is efficient enough.

Code:

int lastStoneWeight(int* stones, int stonesSize) {
    int size = stonesSize;
    
    while (size > 1) {
        // Find the largest stone
        int max1 = 0;
        for (int i = 1; i < size; i++) {
            if (stones[i] > stones[max1]) {
                max1 = i;
            }
        }
        
        // Move largest stone to the end
        int temp = stones[max1];
        stones[max1] = stones[size - 1];
        stones[size - 1] = temp;
        
        // Find the second largest stone
        int max2 = 0;
        for (int i = 1; i < size - 1; i++) {
            if (stones[i] > stones[max2]) {
                max2 = i;
            }
        }
        
        int y = stones[size - 1];
        int x = stones[max2];
        
        if (x == y) {
            // Both stones destroyed
            stones[max2] = stones[size - 2];
            size -= 2;
        } else {
            // Replace second largest with y - x, remove largest
            stones[max2] = y - x;
            size -= 1;
        }
    }
    
    return size == 1 ? stones[0] : 0;
}