Last Stone Weight

Last Stone Weight easy

Description

You’re given an array of positive integers stones representing weights. Each turn:

Pick the two heaviest stones, call them x and y with y >= x.
Smash them together:
- If x == y, both are destroyed.
- If x != y, x is destroyed and y becomes y - x.
Repeat until at most one stone remains.

Return the weight of the last stone, or 0 if the pile is empty.

Examples

> Case 1:
    Input:  stones = [2, 7, 4, 1, 8, 1]
    Output: 1
    # 8,7 → 1; pile becomes [2, 4, 1, 1, 1]
    # 4,2 → 2; pile becomes [2, 1, 1, 1]
    # 2,1 → 1; pile becomes [1, 1, 1]
    # 1,1 → 0; pile becomes [1]
    # Last stone = 1
 
> Case 2:
    Input:  stones = [1]
    Output: 1

Constraints

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

Intuition

We need the two heaviest stones repeatedly. That’s exactly what a max-heap is for.

peek gives us the biggest in O(1).
pop removes and returns it in O(log n).
push adds the difference back in O(log n).

Repeat until the heap has at most one element. We get the answer in O(n log n).

The alternative — sorting after every smash — is O(n² log n). The heap pays for itself the moment n grows.

Try it yourself

⌨ Last Stone Weight — return the final stone's weight (or 0)

def last_stone_weight(stones):
  # Repeatedly smash the two heaviest stones; a max-heap gives them in O(log n).
  pass

Hint

Python's heapq is a min-heap, so negate every weight to get max-heap behavior. Pop the two largest, push back the difference if they differ.

Reveal solution

Code

The Python negation trick is unavoidable because heapq only does min-heaps. Negate everything going in, negate everything coming out — the order between negated values is the reverse of the original, so the smallest negative is the most positive original.

Analysis

Time: O(n log n) — at most n rounds, each doing constant heap operations of O(log n). Initial heapify is O(n).
Space: O(n) for the heap.

Kth Largest in Stream Top K Frequent Elements

Finished this page?