LeetCode Day 13 (Day 12 is rest day) Stack and queue(3/3)

The third day of practice about stack and queue, today are difficult questions.

Question 1

239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

This is the first time I’ve met a Hard difficulty question in so many days, probably because I haven’t completed many questions, I think it’s almost as difficult as Medium.

Use a sliding window to see the maximum value in the current window, and append it to an array that holds the result, and return the array at the end of the program.

The window moves 1 position at a time, regardless of k, so it’s easier to go with the stack idea. However, in further reasoning, it does not feel right, the elements of the stack if pop out, it is possible to remove the maximum value required.

After watching the video explanation, I understand that this problem can be solved by using monotonic queue!

from collections import deque
 
 
class MyQueue: 
    def __init__(self):
        self.queue = deque() 
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()
            
    def push(self, value):
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
        
    def front(self):
        return self.queue[0]
    
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        result = []
        for i in range(k):
            que.push(nums[i])
        result.append(que.front()) 
        for i in range(k, len(nums)):
            que.pop(nums[i - k])
            que.push(nums[i]) 
            result.append(que.front()) 
        return result

Question 2

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

There are three things to implement in this question:

1. To count the frequency of occurrence of elements
2. To sort the frequencies
3. To find the first K high frequency elements

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
 
        map_ = {} 
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i], 0) + 1
        
 
        pri_que = [] 
        
        for key, freq in map_.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k: 
                heapq.heappop(pri_que)
 
        result = [0] * k
        for i in range(k-1, -1, -1):
            result[i] = heapq.heappop(pri_que)[1]
        return result

I’m a bit confused about the top heap in this question, so I’ll come back to it when I’m done with the binary tree part of the question.