# Last Stone Weight

- **Canonical ID**: `last-stone-weight`
- **Canonical URL**: https://dsacheatsheet.com/problems/last-stone-weight
- **Difficulty**: easy
- **Patterns**: Heaps
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/last-stone-weight/

## 1. Core Invariant / The Trick

Simulate greedy extraction of the two heaviest stones using a max-heap (`-val` in Python min-heap): while `len(h) > 1`, pop `y`, pop `x`, and if `y != x` push `y - x`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N log N)`
- **Space Complexity**: `O(N)`
- **Proof**: Each round consumes at least one stone; at most N iterations execute O(log N) heap pops/pushes.

## 3. Minimal Idiomatic Code

### Python
```python
def lastStoneWeight(stones: list[int]) -> int:
    h = [-s for s in stones]
    heapq.heapify(h)
    while len(h) > 1:
        y = -heapq.heappop(h)
        x = -heapq.heappop(h)
        if y != x:
            heapq.heappush(h, -(y - x))
    return -h[0] if h else 0
```

### TypeScript
```typescript
export function lastStoneWeight(stones: number[]): number {
  const h: number[] = [];
  const push = (v: number) => {
    h.push(v);
    for (let i = h.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (h[p] >= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = h[0], last = h.pop()!;
    if (h.length) {
      h[0] = last;
      for (let i = 0; ; ) {
        let b = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < h.length && h[l] > h[b]) b = l;
        if (r < h.length && h[r] > h[b]) b = r;
        if (b === i) break;
        [h[i], h[b]] = [h[b], h[i]];
        i = b;
      }
    }
    return top;
  };
  for (const s of stones) push(s);
  while (h.length > 1) {
    const y = pop(), x = pop();
    if (y !== x) push(y - x);
  }
  return h.length ? h[0] : 0;
}
```

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

### Java
```java
int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    for (int s : stones) pq.offer(s);
    while (pq.size() > 1) {
        int diff = pq.poll() - pq.poll();
        if (diff > 0) pq.offer(diff);
    }
    return pq.isEmpty() ? 0 : pq.peek();
}
```

### Go
```go
func lastStoneWeight(stones []int) int {
    // Max-heap via container/heap
    h := MaxHeap(stones); heap.Init(&h)
    for len(h) > 1 {
        y := heap.Pop(&h).(int); x := heap.Pop(&h).(int)
        if y != x { heap.Push(&h, y-x) }
    }
    if len(h) == 0 { return 0 }
    return h[0]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Returning without `h[0]` sign inversion when using negated values in Python.
- Forgetting empty heap edge case (all stones annihilated -> return 0).

### Follow-ups
- Last Stone Weight II asks for minimum leftover overall, which reduces to 0/1 Knapsack partition (`sum - 2 * subsetSum`).