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.

The game ends when there is at most one stone left. Return the weight of the last remaining stone.

Example 1

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

• We smash 8 and 7, and the remaining stones are [2,4,1,1,1].
• We smash 4 and 2, and the remaining stones are [1,1,1,1].
• We smash 1 and 1, and the remaining stones are [1,1].
• We smash 1 and 1, and the remaining stones are [].
• The last stone is 1.

Example 2

Input: stones = [1] Output: 1

Steps to Solve

1. Use a Priority Queue (Max Heap): A max heap is ideal because we need to efficiently find the two largest stones at each step. Java's PriorityQueue with a custom comparator provides this functionality.
2. Iterative Smashing: While the priority queue contains more than one stone, repeatedly:
   • Remove the two largest stones (x and y).
   • If x != y, add y - x back to the queue.
3. Return the Last Stone: After the loop, if the queue is not empty, the remaining stone is the answer; otherwise, it's 0.

Explanation

The priority queue keeps track of the stones in descending order of weight. By repeatedly removing the two largest stones and either destroying them or replacing them with a smaller stone, we simulate the game's mechanics. The use of a max heap ensures that the heaviest stones are always processed first, making the algorithm efficient.

Code

import java.util.PriorityQueue;

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>( (a, b) -> b - a); // Max heap

        // Add stones to the priority queue
        for (int stone : stones) {
            pq.offer(stone);
        }

        // Simulate smashing stones
        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();
            if (x != y) {
                pq.offer(y - x);
            }
        }

        // Return the weight of the last stone (or 0 if no stones left)
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

Complexity

• Time Complexity: O(N log N), where N is the number of stones. This is dominated by the offer and poll operations of the priority queue, which take O(log N) time each. We perform these operations at most 2N times.
• Space Complexity: O(N) to store the priority queue. In the worst case (all stones are distinct), the queue will hold all stones at once.