Sliding Window Maximum | Leetcode #239

This video explains a very important programming interview problem which is the sliding window maximum.I have explained and compared multiple techniques for this problem from bruteforce to heap and deque.In this problem, given an array and a window size, we are required to return an array of maximum elements for all the windows of given size.First I have explained the bruteforce or naive approach and then optimized the solution using heap data structure.Finally, I have shown the most optimal solution using deque.I have shown all the required intuition using examples.I have also shown CODE for all the explained techniques at the end of the video.

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

==========================================PLEASE DONATE=============================
==============================================================================

=======================================================================
USEFUL LINKS:

RELATED LINKS:

#heap #techdose #deque

[siobhanahbois]

Brute force: 2:22
Heap: 4:21
Deque: 12:58

[ItsZarif]

I watched 5 different videos but yours was the only one that helped me finally understand the deque solution. Thank you!

[shekharchaudhary]

I have watched two of your videos today and I can tell you that the quality of your teaching has increased. Just after understanding both the approaches I felt that I could code on my own and so I did. Thank you very much.

[srikrishnarohanmadiraju]

Thanks! Very comprehensive explanation.
In the third approach using Doubly-LL, I understand that the time complexity is O(N) due to the traversal of the array.
Is there no time consumption for the building of DLL. If the elements are coming in descending order, then we have to build the window size right, so wouldn't that make the complexity O(N+K) (K amortized) . Can you elaborate it a bit more on the time complexity arising during the building of DLL and how it impacts the overall complexity.

[WdnUlikno]

Thank you! I got 57/61 correct, but kept getting Time limited exceeded for the last 4 test cases. When I tried switching to Priority queue implementation, my correct went down to 49/61, still getting Time Limit exceded. This has been driving me crazy ALL day.

[roshanraut]

The explanation was simply Makkhan ie. Hat's

[ahmadalk]

Just honestly one think I didn't like is that with the method fo dequeue:
I actually watched the video in order to understand how this method works but you came up with these steps rather than showing the actual way of problem solving and how we can figure out such steps in similar problems.

Thank you,

[darshitgajjar]

you're awesome. your content is roaring. Big Kudos to U man. make more videos like this. Great 👏

[jenny]

The best video for this leetcode question and it's so easy to follow! THANK YOU!

[fakruu]

Top notch explanation !! thanks for the efforts

[yitingg]

Thank you so much Sir! Finally understood it watching the graph you drew. The third solution is so hard to think of..

[pranavsharma]

Amazing Explanation! Thanks a lot....!!

[sciphilo]

Thanks a ton for this valuable content!! Top notch explanation.

[beaconbecay]

Thank you for the great explanation as usual TECH DOSE. The deque solution does not appear to exactly be O(N). For instance, consider the input: nums = [3, 1, -1, 0, 2, 0, -6, -7] and k = 4. You will notice that you have to pop multiple values (not just one) when you reach index 4. And this can also happen several times in different types of inputs.

[arshadjamal]

Thank you so much for such a valuable content

[AdityaSingh-lfoe]

A map implementation is easier than heap implementation.. All elements in map are sorted just like in heap, but popping the leftmost index of window is much easier in map (map[nums[i-k] -= 1)

[aravindravva]

why to keep index in heap?
because the TC for removal is O(n)
and for push, pop is O(logn)

[umashankarboga]

same question has been asked recently in quotient technologies last month....!!!

[derilraju]

Two methods solutuon, sliding window and heap

from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
return self.heap_method(nums, k)

# sliding window is O(N) method
i = 0
j = 0
que = deque()
ans = []
while j < len(nums):
while que and nums[j] > que[-1]:
que.pop()
que.append(nums[j])
if j-i+1 < k:
j+=1
elif j-i+1 == k:
ans.append(que[0])
if que[0] == nums[i]:
que.popleft()
i+=1
j+=1
return ans

def heap_method(self, nums, k):
# O(NlgK)
nums = [-i for i in nums]
pq = [(val, idx) for idx, val in enumerate(nums[:k])]
heapify(pq)
res = [-pq[0][0]]
for i in range(k, len(nums)):
while pq and pq[0][1] <= i-k: # stale el removal
heappop(pq)
heappush(pq, (nums[i], i))
res.append(-pq[0][0])
return res

[dummydp]

In the heap approach, what is the heap size we should declare.
If its n, then the space complexity will be O(n)..
Or should we declare the heap of size 2k..?
If, we declare heap array of size 2k, then for each heapify, it will take log2k times..
Please clarify once on the heap size what should we declare.. Thanks