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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Last Stone Weight and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →