LC-1046 Easy LeetCode

1046. Last Stone Weight

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 66% Topics: Array, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import heapq


class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        max_heap = [-x for x in stones]
        heapq.heapify(max_heap)
        for i in xrange(len(stones)-1):
            x, y = -heapq.heappop(max_heap), -heapq.heappop(max_heap)
            heapq.heappush(max_heap, -abs(x-y))
        return -max_heap[0]

Solution from kamyu104/LeetCode-Solutions · MIT