Show problems as
Classic problem #1046EasyArrayHeap (Priority Queue)

Last Stone Weight

Real-world version: Molten Glass Merge
Tracked in this browser only
Read Last Stone Weight on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def last_stone_weight(gobs: list[int]) -> int:
Java
public int lastStoneWeight(int[] gobs)

More on the same topics