Maximum of all subarrays of size K | Leetcode #239

This video explains a very important interview question which is to find the maximum values in all subarrays of size K. I have explained the brute-force as well as the efficient approach with intuition taking proper example. I have explained using a doubly linked list which can be implemented easily using the dequeue STL. As usual, the CODE LINK is given below. 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 :)

[saurabhsengar]

sir if we try for 4, 1, 3, 2, 6 and k=3
then for 2nd itteration when window size if 1, 3, 2 the maximum comes out to be 2 accordding to this algo
plzz explain ....

[sulaxnagupta]

Thank you very much !!! I had 2 doubts . Both r solved .
reason why the indices were stored was to access them directly when needed .
Elements stored in increasing indices order that's y we can just pop elements from front for the elements out of the window.


This video helped me a lot!

[venkatachaitanyayadla]

but, in worst case, the size of the linked list may go to k (window size)and we are doing k comparisons .
then the time complexity becomes O(n.k) again?
then what's the use of this alg.?

[lapujain]

Hi Sir, Your daily leetcode videos are the most inspirational thing for me to learn new things everyday, from last 1 Month I have not missed your single video. I really appreciate your work. If you have time can you please make video on Time complexities, its really hard for newbies like me to understand/calculate the accurate complexities for a program. Thanks in advance.

[karumanchikartheek]

@Techdose at 01:58 the maximum possible subarrays was (N-K)+1 so please correct it

[DK-oxze]

You have just given the algorithm (how) and not explained the reasoning (why). This is not very helpful as it promotes rote learning and your ability to replicate it later is dependent on your memory, not your understanding.

[mohnishsinghbhamra]

According to the algo explained, for input [9, 10, 9, -7, -4, -8, 2, -6] & k=5
code output will be [10, 10, 2, 2] . however expected output would be [10, 10, 9, 2].
Meaning we have to start deque process even at the first window while finding max

[RishiRaj-dlmg]

At 6:27 how the index no "1" was popped out of deque. It's value is greater than or equal to current value, so it shouldn't be popped out. Right?

[souravchoudhary]

I have seen where questions can be solves using a queue or deque, you implement it using a list or DLL. It's not bad but the implementation becomes much more simpler in handling queue as compared to DLL. Thanks for your vdos tho. They help a lot in learning. ❤️

[tanmayvaish]

We will have (n-k+1) subarrays/windows, not (n-k)!!!

[willturner]

Watched 2 times but understand your approach😊

[jackcary]

Thanks. However, in your second example, what if the value on #2 index is 5 (meaning [1, 6, 5, 3, 4, 1]? 5 will not be pushed into deque, and thus it will be missing. But 5 should be the biggest of [5, 3, 4]

[nagarjuna]

I think 'why' you do the operations u explained is missing. eg.. why do we need push only if rear is greater than current element

[saneethvarma]

Can't we use hashmap with frequencies ?

[niveditamishra]

Your solution does not seem to be working for given input : A = [9, 10, 9, -7, -4, -8, 2, -6] and k = 5

[namanvijay]

great explaination, do mention how to make list for 1st window in description

[shauvikpujari]

Sir Your Code in GitHub link is not acceptable in leetcode

[soumavanag]

Can you help in explaining "Find maximum of minimum for every window size in a given array"?

[saritasrivastava]

Can we solve this by taking max heap of size k and print max when size of heap become more than k

[supernova]

Sir, please make videos based on implementation of binary search, as i am unable to apply that logic in many of the problems.