09 Sept 2026•Go / Python / TypeScript•Easy

Last Stone Weight

Repeatedly smash the two heaviest stones and return the remaining weight.

View original LeetCode question

Maintain a max heap so each round can remove the two largest stones and restore their positive difference.

complexity

O(n log n) time and O(n) heap space.

solution files

Go last-stone-weight/solution.go
Python last-stone-weight/solution.py
TypeScript last-stone-weight/solution.ts

Solution files

Go•last-stone-weight/solution.go

package main

import "container/heap"

type maxHeap []int

func (values maxHeap) Len() int               { return len(values) }
func (values maxHeap) Less(i int, j int) bool { return values[i] > values[j] }
func (values maxHeap) Swap(i int, j int)      { values[i], values[j] = values[j], values[i] }
func (values *maxHeap) Push(value any)        { *values = append(*values, value.(int)) }
func (values *maxHeap) Pop() any {
	old := *values
	last := old[len(old)-1]
	*values = old[:len(old)-1]
	return last
}

func lastStoneWeight(stones []int) int {
	stonesHeap := maxHeap(stones)
	heap.Init(&stonesHeap)
	for stonesHeap.Len() > 1 {
		first := heap.Pop(&stonesHeap).(int)
		second := heap.Pop(&stonesHeap).(int)
		if first != second {
			heap.Push(&stonesHeap, first-second)
		}
	}
	if stonesHeap.Len() == 0 {
		return 0
	}
	return heap.Pop(&stonesHeap).(int)
}

Python•last-stone-weight/solution.py

import heapq


class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-stone for stone in stones]; heapq.heapify(heap)
        while len(heap) > class="syntax-number">1:
            first, second = -heapq.heappop(heap), -heapq.heappop(heap)
            if first != second: heapq.heappush(heap, second - first)
        return -heap[class="syntax-number">0] if heap else class="syntax-number">0

TypeScript•last-stone-weight/solution.ts

function lastStoneWeight(stones: number[]): number {
  const heap: number[] = [];
  const push = (value: number): void => { heap.push(value); let index = heap.length - class="syntax-number">1; while (index > class="syntax-number">0) { const parent = Math.floor((index - class="syntax-number">1) / class="syntax-number">2); if (heap[parent] >= heap[index]) break; [heap[parent], heap[index]] = [heap[index], heap[parent]]; index = parent; } };
  const pop = (): number => { const root = heap[class="syntax-number">0]; const last = heap.pop(); if (heap.length && last !== undefined) { heap[class="syntax-number">0] = last; let index = class="syntax-number">0; while (true) { const left = index * class="syntax-number">2 + class="syntax-number">1; const right = left + class="syntax-number">1; let largest = index; if (left < heap.length && heap[left] > heap[largest]) largest = left; if (right < heap.length && heap[right] > heap[largest]) largest = right; if (largest === index) break; [heap[index], heap[largest]] = [heap[largest], heap[index]]; index = largest; } } return root; };
  for (const stone of stones) push(stone);
  while (heap.length > class="syntax-number">1) { const first = pop(); const second = pop(); if (first !== second) push(first - second); }
  return heap[class="syntax-number">0] ?? class="syntax-number">0;
}