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 stone of weight x is destroyed, and the stone of weight y - x is added to the array.

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 left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1] Output: 1 Explanation:

  • We combine 8 and 7, getting 1. The array becomes [2,4,1,1,1].
  • We combine 4 and 2, getting 2. The array becomes [2,1,1,1].
  • We combine 2 and 1, getting 1. The array becomes [1,1,1].
  • We combine 1 and 1, getting 0. The array becomes [1].
  • The last stone has weight 1.

Example 2:

Input: stones = [1] Output: 1

Steps

  1. Sort: Sort the stones array in descending order. This allows us to easily find the two heaviest stones.
  2. Iterate: While there are at least two stones in the array:
    • Take the two heaviest stones (first two elements).
    • Smash them: Calculate the difference (or 0 if they are equal).
    • Add the result (if non-zero) back into the array.
    • Sort the array again to maintain the descending order.
  3. Return: After the loop, if the array is empty, return 0. Otherwise, return the weight of the single remaining stone (the only element in the array).

Explanation

The algorithm uses a greedy approach. By repeatedly smashing the two heaviest stones, we ensure that we make progress towards reducing the number of stones. Sorting after each smash maintains the efficiency of finding the heaviest stones in O(1) time (as they are always at the beginning of the sorted array). The use of a PriorityQueue could also improve time complexity for very large inputs compared to repeatedly sorting.

Code (TypeScript)

function lastStoneWeight(stones: number[]): number {
    stones.sort((a, b) => b - a); // Sort in descending order

    while (stones.length > 1) {
        const y = stones[0];
        const x = stones[1];
        stones.splice(0, 2); // Remove the two heaviest stones

        const diff = y - x;
        if (diff > 0) {
            stones.push(diff);
            stones.sort((a, b) => b - a); // Resort after adding the new stone
        }
    }

    return stones.length === 0 ? 0 : stones[0];
};

Complexity

  • Time Complexity: O(N log N), dominated by the sorting operations. The while loop iterates at most N times.
  • Space Complexity: O(log N) in the best case if the sort is in-place (like sort in most JavaScript implementations), otherwise, it could be O(N) if a copy is made during the sort. The extra space used by the array is relatively small compared to the input size.