LC 239 & LC 347 & LC 973

Solution to LeetCode 239 Sliding Window Maximum & LeetCode 347 Top K Frequent Elements & LeetCode 973 K Closest Points to Origin.

LeetCode 239

Sliding Window Maximum (Hard) [link]

Brute Force Solution. Time complexity O(n*k).

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        res = []
        for i in range(n-k+1):
            MAX = max(nums[i:i+k])
            res.append(MAX)
        return res

Using Monotonic Queue, elements in Queue are in decreasing order. For example, a window [2,3,5,1,4] in the Queue is [5,4]. Time complexity O(n). Space complexity O(k).

Initial idea:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = deque()
        res = []
        for i in range(k):
            while que and nums[i] > que[-1]:
                que.pop()
            que.append(nums[i])
        res.append(que[0])

        for i in range(k, len(nums)):
            if nums[i-k] == que[0]:
                que.popleft()
            while que and nums[i] > que[-1]:
                que.pop()
            que.append(nums[i])
            res.append(que[0])
            
        return res

Implement a customized Monotonic Queue.

class MyQueue():
    def __init__(self):
        self.queue = []
    
    def pop(self, value):
        # move window and remove the first element
        if self.queue and self.queue[0] == value:
            self.queue.pop(0)

    def push(self, value):
        # keep descending order
        while self.queue and self.queue[-1] < value:
            self.queue.pop()
        self.queue.append(value)

    def front(self):
        # return the max
        return self.queue[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        res = []
        for i in range(k):
            que.push(nums[i])
        res.append(que.front())
        for i in range(k, len(nums)):
            que.pop(nums[i-k])
            que.push(nums[i])
            res.append(que.front())
        return res

Using max-heap. Time complexity O(n log n). Space complexity O(k).

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
                # elements in heap are in increasing order by default in python
          q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        res = [-q[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(q,(-nums[i], i))
            while q[0][1] <= i-k:
                heapq.heappop(q)
            res.append(-q[0][0])
        return res

LeetCode 347

Top K Frequent Elements. (Medium) [link]

Using min-heap. Every time we pop the smallest number and only keep the k max numbers in the heap.

Note that dictionary is not subscriptable so we cannot create the queue with k element, heapify it, and within the loop doheappushpop(). Instead, we need to pop whenever the size reaches the k within the loop.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # frequency of nums
        cnt = {}
        for i in nums:
            if i not in cnt:
                cnt[i] = 1
            else:
                cnt[i] += 1
        
        # min heap
        que = []
        for num, freq in cnt.items():
            heapq.heappush(que, (freq, num))
            if len(que) > k:
                heapq.heappop(que)
        res = []
        for i in range(k-1, -1, -1):
            res.append(que[i][1])
        return res

LeetCode 973

K Closest Points to Origin (Medium) [link]

1] Python Sort. Sort the points by their Euclidean distances to the origin. Time complexity O(n log n). Space complexity O(log n) needed by sorting.

The .sort python function is based on the Time sort algorithm which was created by Tim peters. This particular soring algorithm is a hybrid sorting algorithm based on insertion and mergesort algorithms internally. The time complexity in best case is O(n), average case is O(n log n), worse case is O(n log n). The space complexity is O(n).

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key = lambda x: x[0]**2 + x[1]**2)
        return points[:k]

2] maxHeap. Because we are looking for the top k closest points to the origin, i.e. the k smallest distances. We need a max heap to store the k smallest distances. Whenever we add a distance into the heap, it will pop out the currently largest distance. The usefulness of maxHeap is that it can determine the current max/min and pop it out. In the end, what remains in the heap is the smallest k distances.

Time complexity O(n log k). Each pop or push operation take time O(log k). Space complexity O(n).

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        q = [(-x ** 2 - y ** 2, i) for i, (x,y) in enumerate(points[:k])]
        heapq.heapify(q)

        n = len(points)
        for i in range(k,n):
            x, y = points[i]
            dist = -x**2 - y**2
            heapq.heappush(q, (dist,i))
            heapq.heappop(q)
            # heapq.heappushpop(q, (dist,i))
        ans = [points[ind] for (_, ind) in q]
        return ans