Last Stone Weight

EasyHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array stones of positive integer weights. Repeatedly pick the two heaviest stones and smash them together. If they weigh the same, both are destroyed. Otherwise the lighter one is destroyed and the heavier one's weight drops by the lighter one's weight, and the survivor goes back into the pile. The process stops when at most one stone remains. Return the weight of the remaining stone, or 0 if no stones are left. Aim for O(n log n) time using a priority queue.

Examples

Input: stones = [2,7,4,1,8,1]
Output: 1
Smash 8 and 7 -> 1; smash 4 and 2 -> 2; smash 2 and 1 -> 1; smash 1 and 1 -> nothing; one stone of weight 1 is left.
Input: stones = [3,3]
Output: 0
The two stones are equal, so both are destroyed and nothing remains.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems