Sliding Window Maximum - Monotonic Queue - Leetcode 239

0:00 - Read the problem
2:20 - Drawing Solution
12:05 - Coding solution

leetcode 239

#product #apple #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[PippyPappyPatterson]

The tricky, and didactic, part of this problem is to store index, rather than value, in the deque— which enables you to tell when the bottom of the deque is outside the window.

[Hangglide]

Why you give two sorted array for examples? (1, 2, 3, 4 and later 1, 1, 1, 1, 4, 5) I found it is very hard to follow when you are using sorted array in the example. Why not use 1, 1, 4, 5, 1, 1 instead so that we can see all cases?

[akshaibaruah]

the best part is even if I figure out the solution after struggling, I still come to see your explanation because it's just so beautiful

[shoooozzzz]

Finally, the monotonic queue data structure makes sense!!! Thank you

[charleskorey]

LC solution is not this elegant as yours. Thanks so much! I was getting stuck on this especially the part where we have to start moving left and right together. In the LC solution, they take care of adding the first k element in the deque separately but your approach is simple and works.

[brecoldyls]

Very cool! Now I am curious to try and apply this data structure to other problems 🤔

[moveonvillain]

I was wondering why it was so easy to figure out at first. Good thing I decided to head here after implementing the brute force solution.

[robertjensen]

Thanks! Small suggestion: `l` can just be `r - k + 1`, which will still do the right thing for the first k elements where it is negative.

[burhanuddinmerchant]

The condition to check whether the window is of the right size or not is incorrect, it should be "(r-l+1)>=k" instead, it worked in your case, but isn't working now, I suppose they have updated the test cases accordingly. Hope it helps someone who might get stuck at this step. Great explanation given none the less

[dansun]

This is very helpful, thanks so much for sharing it!!

[iamsmitthakkar]

If you're like me and the condition "if l > dq[0]:" confuses you, you can rather use "if dq[0] < (r-k+1):" which makes better sense since we are checking if our window is out of bound by checking the first index of dq and r(current indxex) and k

[ChanChan-pgwu]

Always the best, thank you, Neet! I watched your video 3 times to understand the problem.

[novasideias]

Man, I really thank you, is 1:58 of the video and I already solved the problem in my mind, while I am in the toilet after wake up😂, the last two days I did 20 problems and whatched your video to understand the solutions that I did not understand

[bombrman]

I solved this with the naive way within like 10 minutes, but then watched your video and looked around solutions and chatGPT to study the optimal solution but I could not understand it when i was walking through the code I was keep losing track of the logic. I gave up and went to bed and next morning gave it another shot on pen and papper approach until i figured it out. I hope I dont get these kind of questions on my interviews cuz this can be disheartening and draining

[stunning-computer-]

i must say guys i am not getting this at all surprisingly i am just blank

[rohanvishayal]

This is my first hard problem that I solved by myself, I didn't use deque instead kept tracking the currentMaxIndex manually and updating it manually when it goes out of the window, the solution I wrote is pretty inefficient ( beats 9% LOL) but I did it, my first hard problem, here to check how to solve it properly. Thank you for the explanation.

[piyusharora]

Thank you NeetCode for this video. I am able to identify the redundancies in the ccalculations of maximum. The use of a deque is genius

[arminphulkar]

This problem breaks the common misconception that the window in the sliding window always have to be an array/vector/list, which is not true, look at it, it's a double ended queue, aka. deque!

[sdaiwepm]

To select my teacher going forward, I watched all the videos explaining this problem #239. Your explanation is the best by far. Thank you!

[colemanlyski]

DJ Khaled been real quiet since 4:20 dropped...