Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

132. Last Stone Weight

EasyDay 39 of 60Heap / Priority Queue

You have a pile of stones with weights stones[i]. Each turn, take the two heaviest stones x <= y and smash them: if they are equal both are destroyed, otherwise the lighter one is destroyed and the heavier one becomes y - x. Repeat until at most one stone is left. Return its weight, or 0 if no stones remain.

Example 1
Input: stones = [2,7,4,1,8,1]
Output: 1
Smash 8 and 7 to get 1, then 4 and 2 to get 2, then 2 and 1 to get 1, then 1 and 1 to get nothing. One stone of weight 1 is left.
Example 2
Input: stones = [1]
Output: 1
Constraints
  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000
Hints
Frequently asked at: Amazon, Google
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min