Last Stone Weight

last-stone-weight.py

#https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3297/
class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        while len(stones) > 1:
            stones.sort()
            new_value = stones.pop() - stones.pop()
            if new_value == 0:
                pass
            else:
                stones.append(new_value)

        if len(stones) == 1:
            return stones[0]
        else:
            return 0

Two things:

1. I would recommend you to take a look at Priority queues and understand how they work. It is a tree-like data structure that keeps the smallest (or the largest) element at the top at all times, meaning that you can remove the element at the top in constant time, it will also take care of arranging the new elements so that the order is kept. Using a priority queue here would prevent you from keeping re-ordering the array (line 9) which makes your algorithm O(n^2)

2. You could replace the if statement in lines 11 to 14 with something like:

if new_value > 0:
    stones.append(new_value)