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 left, 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 is now [2,4,1,1,1]. We combine 4 and 2 to get 2. The array is now [2,1,1,1]. We combine 2 and 1 to get 1. The array is now [1,1,1]. We combine 1 and 1 to get 0. The array is now [1]. The last stone has weight 1.

Example 2

Input: stones = [1] Output: 1

Steps

1. Sort the stones: We need to efficiently find the two heaviest stones. Sorting the array allows us to access them directly at the end.
2. Iterate until one stone or less remains: While there are at least two stones, we pick the two heaviest, smash them, and update the array. We use a priority queue (MaxHeap) for efficient retrieval of the heaviest elements.
3. Return the weight: After the loop, if there's one stone left, its weight is the answer; otherwise, return 0.

Explanation

The solution uses a MaxHeap (priority queue) to efficiently manage the stones. A MaxHeap ensures that the heaviest stone is always at the top, allowing for O(1) access to the heaviest element. Removing and adding elements takes O(log n) time, where n is the number of stones.

The algorithm iteratively picks the two heaviest stones, performs the smash operation, and re-inserts the resulting stone (if any) back into the heap. This continues until only one or zero stones remain.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int LastStoneWeight(int[] stones) {
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>(); // MaxHeap
        foreach (int stone in stones) {
            pq.Enqueue(stone, -stone); // Use negative value for max heap
        }

        while (pq.Count > 1) {
            int y = pq.Dequeue(); //Heaviest
            int x = pq.Dequeue(); //Second Heaviest

            int diff = -y - (-x); // Calculate difference using negative values from max heap
            if (diff > 0) {
                pq.Enqueue(diff, -diff); //Add back the resulting stone if difference is greater than 0
            }
        }

        return pq.Count == 1 ? pq.Dequeue() : 0;
    }
}

Complexity

• Time Complexity: O(N log N), where N is the number of stones. This is dominated by the sorting step (using a priority queue).
• Space Complexity: O(N) in the worst case to store the priority queue. The space used for sorting can vary depending on the sorting algorithm. The use of PriorityQueue provides efficient management of the stones as opposed to repeated sorting of an array.