Snowball Showdown

EasyheapAlso known as Last Stone Weight

A winter fair runs a snowball machine game. The machine holds a pile of packed snowballs of different sizes. Each round, it fires the two biggest snowballs straight at each other.

If they are the same size, both shatter. If not, the smaller one shatters and knocks that much snow off the bigger one, which drops back into the pile with its new size. The crowd bets on what is left when fewer than two snowballs remain.

Your task

Write lastSnowball(sizes). Run the rounds described above until fewer than two snowballs are left. Return the size of the one that remains, or 0 if none remain.

In a round where the two biggest have sizes a ≥ b: if a = b both disappear, otherwise a snowball of size a - b goes back into the pile.

lastSnowball(sizes: int[]) → int

Examples

Example 1

Input

sizes = [4, 9, 2, 6]

Output

Why

9 and 6 collide: 3 goes back, pile [4, 2, 3]. 4 and 3 collide: 1 goes back, pile [2, 1]. 2 and 1 collide: 1 goes back. One snowball of size 1 is left.

Example 2

Input

sizes = [5, 5, 3, 3]

Output

Why

5 and 5 shatter each other. Then 3 and 3 shatter each other. Nothing is left, so the answer is 0.

Example 3

Input

sizes = [7]

Output

Why

With only one snowball there is no round at all. The answer is 7.

Constraints

1 ≤ sizes.length ≤ 100,000
1 ≤ sizes[i] ≤ 1,000,000

Start with brute force

Sort the pile, take the two biggest from the end, put the difference back, and sort again. Repeat.

Each sort costs O(n log n), and there can be up to n rounds, so the total is O(n² log n). With 100,000 snowballs that is far beyond a billion steps. Even inserting the leftover into a sorted array in the right place costs O(n) per round because of shifting, so O(n²) overall.

Hints

0 of 4 shown

Hint 1
In the first example, after 9 and 6 collide, a 3 goes back. Where does the 3 belong among the remaining sizes? Could the leftover ever be the biggest in the pile next round?
Hint 2
Every round you need the two largest of a pile that keeps changing: two items leave and maybe one comes back with a new size. Sorting the pile again after every round redoes almost all of the work.
Hint 3
Which data structure hands you the largest item quickly and lets you add a new item quickly, without keeping everything fully sorted?
Hint 4
Use a max-heap. Push every size. While it holds at least two: pop a, pop b, and if a > b push a - b. At the end return the top if one is left, otherwise 0. (Python's heapq is a min-heap; store negated sizes.)

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The rule "always take the biggest two" is a job for a max-heap. It gives you the largest item in O(log n) and accepts a new item in O(log n), without ever sorting the whole pile.

Trace [4, 9, 2, 6]:

Heap holds 9, 6, 4, 2. Pop 9 and 6. 9 > 6, push 3. Heap: 4, 3, 2.
Pop 4 and 3. Push 1. Heap: 2, 1.
Pop 2 and 1. Push 1. Heap: 1.
Only one left. Return 1.

Every round removes at least one snowball for good, so there are at most n - 1 rounds. The JavaScript version writes the heap by hand because the language has none built in; it is the same sift-up and sift-down you learn in the heaps lesson.

Reference solution

function lastSnowball(sizes) {
  const heap = []; // max-heap: heap[0] is the biggest
  const push = (x) => {
    heap.push(x);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] >= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = l + 1;
        let big = i;
        if (l < heap.length && heap[l] > heap[big]) big = l;
        if (r < heap.length && heap[r] > heap[big]) big = r;
        if (big === i) break;
        [heap[big], heap[i]] = [heap[i], heap[big]];
        i = big;
      }
    }
    return top;
  };
 
  for (const s of sizes) push(s);
  while (heap.length >= 2) {
    const a = pop(); // biggest
    const b = pop(); // second biggest
    if (a > b) push(a - b);
  }
  return heap.length ? heap[0] : 0;
}

import heapq
 
def last_snowball(sizes):
    # heapq is a min-heap, so store negated sizes
    heap = [-s for s in sizes]
    heapq.heapify(heap)
    while len(heap) >= 2:
        a = -heapq.heappop(heap)  # biggest
        b = -heapq.heappop(heap)  # second biggest
        if a > b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

TimeO(n log n)Up to n - 1 rounds, each with at most two pops and one push at O(log n).

SpaceO(n)The heap holds every snowball.

Learn the idea: Heaps and Priority Queues Heap Sort

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code