Last Stone Weight

easy heap priority queue

Problem

Each turn, pick the two heaviest stones y ≥ x. If y == x, both shatter. Otherwise the remainder y − x returns. Repeat until at most one stone remains. Return its weight (or 0 if none).

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

Output1

8-7=1 → [2,4,1,1,1]; 4-2=2 → [2,1,1,1]; 2-1=1 → [1,1,1]; 1-1=0 → [1]. Answer 1.

stones (comma-separated, non-negative)

import heapq
def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        y = -heapq.heappop(heap)
        x = -heapq.heappop(heap)
        if y != x:
            heapq.heappush(heap, -(y - x))
    return -heap[0] if heap else 0

function lastStoneWeight(stones) {
  // simple max-heap via sorted array for clarity
  const heap = stones.slice().sort((a, b) => b - a);
  while (heap.length > 1) {
    const y = heap.shift();
    const x = heap.shift();
    if (y !== x) {
      const d = y - x;
      let i = heap.findIndex(v => v <= d);
      if (i === -1) i = heap.length;
      heap.splice(i, 0, d);
    }
  }
  return heap[0] || 0;
}

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) heap.offer(s);
        while (heap.size() > 1) {
            int y = heap.poll();
            int x = heap.poll();
            if (y != x) heap.offer(y - x);
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> heap(stones.begin(), stones.end());
    while (heap.size() > 1) {
        int y = heap.top(); heap.pop();
        int x = heap.top(); heap.pop();
        if (y != x) heap.push(y - x);
    }
    return heap.empty() ? 0 : heap.top();
}

Explanation

Each turn we smash the two heaviest stones together. Because we always need the two biggest, a max-heap is the perfect tool — its top is always the heaviest stone.

We put all stones into a max-heap. (Python only has min-heaps, so we store -stone and negate again when we read.) Then we loop while more than one stone remains.

Each round we pop the two largest, call them y and x with y ≥ x. If they are equal they both shatter and nothing returns. If y > x, the leftover y - x goes back into the heap as a new stone.

When the loop ends, at most one stone is left; we return its weight, or 0 if the heap is empty.

Example: stones=[2,7,4,1,8,1]. Smash 8 and 7 → 1 returns; then 4 and 2 → 2 returns; then 2 and 1 → 1 returns; then 1 and 1 → both shatter; one stone of weight 1 remains, so the answer is 1.

Time: O(n log n) Space: O(n)