Day 24 of LeetCode

Documenting LeetCode solving.

Q74

1046. Last Stone Weight

Easy. Max queue

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-s for s in stones]
        heapq.heapify(stones)

        while len(stones) > 1:
            first = heapq.heappop(stones)
            second = heapq.heappop(stones)
            if second > first:
                heapq.heappush(stones, first - second)

        // edge case, no items in the queue
        heapq.heappush(stones, 0)
        return abs(stones[0])

Q75

973. K Closest Points to Origin

Medium. Min heap

Pop the first k in the min heap.

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        minHeap = []
        for x, y in points:
            dist = (x ** 2) + (y ** 2)
            minHeap.append([dist, x, y])
        heapq.heapify(minHeap)

        res = []
        while k > 0:
            dist, x, y = heapq.heappop(minHeap)
            res.append([x, y])
            k -= 1

        return res

Q76

621. Task Scheduler

Medium. Max heap + queue

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # count = {}
        # for t in tasks:
        #     count[t] = count.get(t, 0) + 1

        # Built in function to get count map
        count = Counter(tasks)
        # Always process the most frequent task first
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        # A queue to track unfinished tasks
        q = deque() # pair [-cnt, idletime]
        time = 0
        while maxHeap or q:
            time += 1
            if maxHeap:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    q.append([cnt, time + n])

            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])

        return time