1046. Last Stone Weight — LeetCode(Python)

I got you!

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, and
• 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.

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

Constraints:

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

Solution:

Explanation —

We can easily solve this problem by using a maxheap.

Python traditionally, only allows us to create minheaps. So a simple way to create a maxheap in Python is to use the negative of a number, to change the ordering.

Now that we have created our maxheap, we iterate the following process until there is only one element left in the array —

• We pop the first two elements from the heap.
• If, both are unequal, we push the difference between the two into our heap, otherwise we continue with the iteration as we we have already popped the consecutive identical stones.

Then, we push a zero to our heap, because we should return a zero if all stones were destroyed.

Finally, we return the root of the heap which is also the min element.

Time and Space Complexity —

Creation of the heap is a linear time operation. And, pushing and popping from a heap require logarithmic time.

Note that we are popping every element from the list and possibly pushing some values in as well.

Thus, if n is the length of the array nums,

Time Complexity: O(nlogn)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏