LeetMotion
You are given an array of integers stones where stones[i] represents the weight of the ith stone.
We want to run a simulation on the stones as follows: At each step we choose the two heaviest stones, with weight x and y and smash them together.
x == y, both stones are destroyed.x < y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.Continue the simulation until there is no more than one stone remaining. Return the weight of the last remaining stone or return 0 if none remain.
We smash 6 and 4 and are left with a 2, so the array becomes [2,3,2,2]. We smash 3 and 2 and are left with a 1, so the array becomes [1,2,2]. We smash 2 and 2, so the array becomes [1].
1 <= stones.length <= 201 <= stones[i] <= 100Why do it this way? To find the two heaviest stones, we can just sort the array and pick the last two. If we smash them and a new stone is formed, we append it, and sort again! It is incredibly easy to understand, but very slow because sorting an entire array repeatedly takes O(N log N) per step, resulting in O(N² log N) overall.
Imagine you need the highest two cards from a deck. You sort the entire deck, take the top two, combine them, put the result back, and then re-sort the entire deck from scratch just to find the next two highest. It works perfectly but is quite tedious!
function lastStoneWeight(stones):
while len(stones) > 1:
stones.sort()
stone1 = stones.pop()
stone2 = stones.pop()
if stone1 != stone2:
stones.append(abs(stone1 - stone2))
return stones[0] if stones else 0Why do it this way? Instead of sorting the entire array from scratch every time, we can recognize that the array is already mostly sorted! When we smash the top two stones and get a remainder, we only need to insert this single new stone back into the sorted array. By using Binary Search, we can find the correct insertion index in O(log N) time, making it faster than a full sort.
Imagine you have an alphabetically sorted stack of graded papers. If a student hands in a late paper, you don't shuffle the whole stack and re-sort it. You simply fan through the stack, find the correct alphabetical spot (Binary Search), and slot it in!
function lastStoneWeight(stones):
stones.sort()
while len(stones) > 1:
cur = stones.pop() - stones.pop()
if cur > 0:
// Find insertion point via binary search
pos = binary_search(stones, cur)
stones.insert(pos, cur)
return stones[0] if stones else 0Why do it this way? To dynamically repeatedly extract the maximum value and insert new values, a Priority Queue (Max-Heap) is the perfect data structure. It allows us to fetch the heaviest stone in O(1) and insert the new shattered pieces in O(log N) without shifting arrays or sorting arrays. Note: in Python, since it only has a Min-Heap, we negate the values to simulate a Max-Heap!
Imagine a tournament where the two heaviest wrestlers must always fight each other first. A Max-Heap is like an automatic organizer that ensures the heaviest guys are always waiting at the front of the line. When they fight, the winner loses some weight and is thrown back into the line, and the organizer instantly bubbles him to his new correct rank.
function lastStoneWeight(stones):
maxHeap = build_max_heap(stones)
while maxHeap.size > 1:
first = maxHeap.pop_max()
second = maxHeap.pop_max()
if first > second:
maxHeap.push(first - second)
return maxHeap.pop_max() if maxHeap else 0Why do it this way? If you look at the constraints, the maximum stone weight is only 100! Whenever data has a tiny maximum value, we can abandon sorting entirely and use a frequency map (Bucket Sort). We just count how many stones we have of each weight from 1 to 100, then iterate backwards from 100, cancelling out pairs of stones at the same weight and carrying over remainders. This brings time complexity down from O(N log N) to linear time!
Imagine you have a giant pile of coins. Instead of laying them all out and sorting them from smallest to largest, you just toss all the quarters into the "Quarter Jar", dimes into the "Dime Jar", etc. You can then just pull coins from the highest-value jars downwards. It's incredibly fast because the number of jars (weight range) is so small!
function lastStoneWeight(stones):
max_weight = max(stones)
buckets = array of size (max_weight + 1) initialized to 0
for weight in stones:
buckets[weight] += 1
i = max_weight
while i > 0:
if buckets[i] == 0:
i -= 1
else:
buckets[i] %= 2 // cancel pairs
if buckets[i] == 1:
j = i - 1
while j > 0 and buckets[j] == 0: j -= 1
if j == 0: return i
buckets[j] -= 1
buckets[i - j] += 1
i -= 1
return 0
Discussion
…