Sliding Window Maximum

'''
M-1
Logic:(similar to skyline problem)
We will have a max heap and a map which will store the window elements as keys.
first insert first window and find it's max and put into _max and answer vector.
whenver you get a new number,push it into the queue,update the max and update
the map.if max_element is same as the previous element before the start of window
let's say prev, then it is possible that prev is not in the new window so get the
maximum number present in the window using the max heap and map and update the
_max and push it into the answer vector.

Insertion in a heap takes log(n) time and for all elements you are pushing so nlog(n) time complexity with O(k+N) worst time complexity
'''
import heapq
from collections import defaultdict
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        mp = defaultdict(int)     # frequency map
        heap = []                 # max heap using negatives
        ans = []

        _max = nums[0]
        i = 0

        # initialize first window
        for i in range(k):
            _max = max(_max, nums[i])
            mp[nums[i]] += 1
            heapq.heappush(heap, -nums[i])

        ans.append(_max)

        # slide the window
        for i in range(k, len(nums)):
            # add new element
            heapq.heappush(heap, -nums[i])
            _max = max(_max, nums[i])
            mp[nums[i]] += 1

            # remove outgoing element
            outgoing = nums[i - k]
            mp[outgoing] -= 1

            # if outgoing was current max, clean heap
            if outgoing == _max:
                while heap and mp[-heap[0]] == 0:
                    heapq.heappop(heap)
                _max = -heap[0]

            ans.append(_max)

        return ans
#M-2 O(n) time and O(k) space
'''
We are not keeping the track of the current window elements and only remove the left most element of the deque if that element is i-kth elment so can an expired element influence our answer? No,because if the i-kth element is not at the deque[0]th element means it has been already popped out of the deque.
'''
from collections import deque
class Solution:
    def maxSlidingWindow(self, arr: List[int], k: int) -> List[int]:
        dq=deque()
        ans=[]
        for i in range(len(arr)):
            if len(dq)>0 and i>=k and dq[0]==arr[i-k]:#remove the top element if it is highest of the immediate last window
                dq.popleft()

            while len(dq)>0 and dq[-1]<arr[i]: # if the number is bigger then we don't need the smaller one,because current number will stay in the window(which is moving forward) till the max time compared to already there in the window and current is already bigger number so current number will take over the max element crown now onwards only so no need of smaller elements.
                dq.pop()
            dq.append(arr[i])
            if i>=k-1:
                ans.append(dq[0])
        return ans;