Last Stone Weight easy

Problem Statement

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.
• If x != y, the resulting stone has weight y - x, and the other stone is destroyed.

At the end of the game, there is at most one stone left. Return the weight of the remaining stone. If there are no stones, return 0.

Example 1

Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1. The array becomes [2,4,1,1,1]. We combine 4 and 2 to get 2. The array becomes [2,1,1,1]. We combine 2 and 1 to get 1. The array becomes [1,1,1]. We combine 1 and 1 to get 0. The array becomes [1]. Thus, we have 1 stone left.

Example 2

Input: stones = [1] Output: 1

Steps

1. Sort: Sort the stones array in descending order. This allows us to easily access the two heaviest stones.
2. Iteration: While there are at least two stones in the array:
   • Get the two heaviest stones (the first two elements).
   • Smash them: Calculate the difference (y - x).
   • Update the array: Remove the two heaviest stones. If the difference is not 0, add the difference back into the array. Re-sort the array.
3. Return: After the loop, if there's one stone left, return its weight. Otherwise (no stones left), return 0.

Explanation

The problem essentially simulates a process of repeatedly smashing the two largest stones until only one or zero stones remain. Using a priority queue (heap) would be a more efficient way to repeatedly find the two largest elements, but for the sake of clarity and simplicity, we'll use sorting in this explanation. Sorting ensures that we always have the two largest stones readily available at the beginning of the array.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lastStoneWeight(vector<int>& stones) {
    if (stones.empty()) return 0;

    while (stones.size() > 1) {
        sort(stones.begin(), stones.end(), greater<int>()); // Sort in descending order
        int y = stones[0];
        int x = stones[1];
        stones.erase(stones.begin()); // Remove the largest stone
        stones.erase(stones.begin()); //Remove the second largest stone

        if (x != y) {
            stones.push_back(y - x); // Add the difference back
        }
    }

    if (stones.empty()) return 0;
    else return stones[0];
}

int main() {
    vector<int> stones1 = {2, 7, 4, 1, 8, 1};
    cout << "Last stone weight (Example 1): " << lastStoneWeight(stones1) << endl; // Output: 1

    vector<int> stones2 = {1};
    cout << "Last stone weight (Example 2): " << lastStoneWeight(stones2) << endl; // Output: 1

    vector<int> stones3 = {};
    cout << "Last stone weight (Example 3): " << lastStoneWeight(stones3) << endl; // Output: 0

    return 0;
}

Complexity

• Time Complexity: O(N log N) per iteration, dominated by sorting. The number of iterations is at most N, resulting in an overall time complexity of O(N^2 log N). However, it is closer to O(N log N) in practice as the number of elements reduces in each iteration.
• Space Complexity: O(1) extra space if we ignore the space used by the input array (in-place sorting). If we consider the space used by the input array, it's O(N). Using a heap would improve this to O(N) for time complexity and O(N) for space complexity.