[Leet Code] Last Stone Weight

Leetcode: https://leetcode.com/problems/last-stone-weight/submissions/

Problem:

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [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 last stone.

Solution:

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        
        while len(stones) > 1:
            heaviest = stones.pop(stones.index(max(stones)))
            second_heaviest = stones.pop(stones.index(max(stones)))
            if heaviest != second_heaviest:
                stones.append(heaviest-second_heaviest)
            
        if len(stones) < 1:
            return 0
        else:
            return stones[0]

Explanation:

We want to check if the length of stones is greater than 1, then we continue into the loop and pop out the heaviest value, then we can pop out the second heaviest value through the same statement (as it is now the heaviest value in the array). Then we check if they’re not equal, we append in the difference of the heaviest and second heaviest values. If they’re equal, they’re already popped out of the array, so we don’t have to do anything else. Then when the array is less than or equal to 1, it checks if the value is less than 1, we return 0, this would happen with a test case of [2,2]. Otherwise, we return the one remaining result in the array.