0386EasyArrayHeap (Priority Queue)

Molten Glass Merge

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A glassworks has a bench of molten gobs; gobs[i] is the weight of gob i in grams.

While at least two gobs are on the bench, the gaffer picks the two heaviest of them, say of weights x and y with x <= y, and presses them together:

if x == y, both gobs are spent and nothing is left of either;
otherwise the pair becomes a single gob weighing y - x grams.

When two gobs tie for heaviest, it does not matter which is picked. Return the weight of the gob left on the bench when no further press is possible, or 0 if the bench ends up empty.

Examples

Example 1

Input: gobs = [3, 7, 2]
Output: 2

Pressing 7 with 3 leaves a 4 gram gob, so the bench holds [4, 2]. Pressing 4 with 2 leaves a 2 gram gob, and that is the last one.

Example 2

Input: gobs = [10, 4, 3, 2]
Output: 1

Pressing 10 with 4 gives [6, 3, 2]; pressing 6 with 3 gives [3, 2]; pressing 3 with 2 leaves a single gram.

Example 3

Input: gobs = [2, 2, 2, 2]
Output: 0

Each press is between equal weights, so the bench ends up empty.

Example 4

Input: gobs = [5]
Output: 5

A single gob has no partner, so no press happens and it stays as it is.

Constraints

1 <= gobs.length <= 30
1 <= gobs[i] <= 1000

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def last_stone_weight(gobs: list[int]) -> int:

Java

public int lastStoneWeight(int[] gobs)

The intended approach

Time O(n log n)Space O(n) for the heap

Only the two heaviest gobs matter at each step and the merged gob has to rejoin the bench, so keep the weights in a heap. Python's heap is a min-heap, so store the negated weights and the two pops give the heaviest pair. Push the difference back whenever it is non-zero, and stop once fewer than two gobs are left.

Pythonentry point: last_stone_weight

import heapq


def last_stone_weight(gobs):
    # Time O(n log n) -- at most n - 1 merges, each a constant number of heap operations.
    # Space O(n) for the heap of negated weights.
    heap = [-weight for weight in gobs]
    heapq.heapify(heap)
    while len(heap) > 1:
        first = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if first != second:
            heapq.heappush(heap, -(first - second))
    return -heap[0] if heap else 0

The obvious version

Re-sort the whole bench before every press and take the last two entries of the sorted list. No heap; the cost is a full sort per press.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_last_stone_weight(gobs):
    bench = list(gobs)
    while len(bench) > 1:
        bench.sort()
        heavy = bench.pop()
        lighter = bench.pop()
        if heavy != lighter:
            bench.append(heavy - lighter)
    return bench[0] if bench else 0

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in