Skip to main content

1046. Last Stone Weight

easy

Simulate smashing the two heaviest stones until at most one remains. A clean warm-up that screams 'max-heap' — the perfect way to demo heap intuition without over-engineering.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is: if x == y, both stones are destroyed; if x != y, the stone of weight x is destroyed and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the weight of the last remaining stone. If there are no stones left, return 0.

Constraints

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

Examples

Example 1

Input
stones = [2,7,4,1,8,1]
Output
1

Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2

Input
stones = [1]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

You always need 'the two heaviest right now'. Sort + re-sort each turn is wasteful.

Hint 2

Max-heap fits perfectly — top is the heaviest, next pop is the second heaviest.

Hint 3

Pop two; if their difference is non-zero, push the difference back. Repeat until <=1 element remains.

Solution approach

Reveal approach

Push every stone into a max-heap. Loop while the heap has at least 2 elements: pop y (heaviest) and x (second heaviest). If x != y, push y - x back. When the loop ends, return the lone remaining element or 0 if the heap is empty. Each iteration is O(log n) push + 2 pops, total O(n log n) for n stones. Many languages only ship a min-heap — push the negation of each stone and negate on read.

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • heap
  • simulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

More Heaps practice problems

See all Heaps problems →