Last Stone Weight

Easy

The problem

Each round, take the two heaviest stones and smash them together. If they weigh the same both vanish; otherwise the lighter one vanishes and the heavier one shrinks by the lighter one's weight. Return the weight of the last stone, or 0 if none is left.

Example 1
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
8 and 7 become 1 → [2, 4, 1, 1, 1]. 4 and 2 become 2 → [2, 1, 1, 1]. 2 and 1 become 1 → [1, 1, 1]. 1 and 1 vanish → [1].
Example 2
Input: stones = [2, 2]
Output: 0

Limits

1 ≤ stones.length ≤ 30
1 ≤ stones[i] ≤ 1000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Each round you need the two heaviest stones. Sorting every round is wasteful.

The idea

Max-heap: pop two, push back their difference if non-zero, repeat until ≤ 1 stone remains.

Target: O(n log n) time

Go function shape

func lastStoneWeight(stones []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LastStoneWeight: each round needs the two heaviest stones, so keep a MAX-heap.
// (Go's heap is a min-heap, so store negated weights.)
func LastStoneWeight(stones []int) int {
	h := &minInts{}
	for _, s := range stones {
		heap.Push(h, -s)
	}
	for h.Len() > 1 {
		a, b := -heap.Pop(h).(int), -heap.Pop(h).(int) // a >= b
		if a != b {
			heap.Push(h, -(a - b))
		}
	}
	if h.Len() == 0 {
		return 0
	}
	return -(*h)[0]
}

Read the lesson: Heap / Top-K