Problem Statement

You are given an array of integers stones where each element represents the weight of a stone. Every turn, you take the two heaviest stones and smash them together:

• If the two stones are equal, both are destroyed.
• If they are not equal, the heavier stone is replaced by the difference of their weights.

This process continues until only one stone is left or no stones are left.

Return the weight of the last remaining stone, or 0 if all stones are destroyed.

Example

Input:

stones = [2,7,4,1,8,1]

Output:

1

Explanation:

• Smash 7 and 8 → result is 1 → stones = [2,4,1,1,1]
• Smash 4 and 2 → result is 2 → stones = [2,1,1,1]
• Smash 2 and 1 → result is 1 → stones = [1,1,1]
• Smash 1 and 1 → both destroyed → stones = [1]
• Final stone = 1

Approach

To always access the two heaviest stones, we use a Max Heap. In Java, PriorityQueue is a Min Heap by default, so to use it as a Max Heap we store negative values.

Steps:

1. Add all stones (as -stone) to a priority queue.
2. While size > 1:
   • Remove two largest stones (y and x)
   • If they are not equal, insert y - x back into the heap.
3. Return the remaining stone (negate it) or 0 if heap is empty.

Java Code

import java.util.PriorityQueue;

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Max Heap using PriorityQueue with reverse order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        // Add all stones to maxHeap
        for (int stone : stones) {
            maxHeap.add(stone);
        }

        // Continue smashing until one or no stone remains
        while (maxHeap.size() > 1) {
            int y = maxHeap.poll(); // heaviest stone
            int x = maxHeap.poll(); // second heaviest

            if (y != x) {
                maxHeap.add(y - x); // insert the result back
            }
            // if y == x, both stones are destroyed; do nothing
        }

        // Return last remaining stone or 0
        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
    }
}

Explanation

• PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
  This creates a max-heap (biggest element at the top).
• maxHeap.poll()
  Removes and returns the largest element.
• If y != x, we insert the difference back to the heap.
• If the heap becomes empty, return 0; otherwise, return the last remaining stone.

Time and Space Complexity

• Time Complexity: O(n log n)
  Each insertion/removal from the heap takes log n time, and we do this for each stone.
• Space Complexity: O(n)
  For storing all stones in the heap.