Sliding Window Maximum | Leetcode

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 225

  • @takeUforward
    @takeUforward  3 роки тому +137

    If you understand it, please do like it, and if possible please spare 2 seconds for a comment :)

    • @anoopraj9319
      @anoopraj9319 3 роки тому

      make videos on dp please

    • @JohnWick-kh7ow
      @JohnWick-kh7ow 3 роки тому

      What's the difference between deque and list?

    • @PrinceKumar-el7ob
      @PrinceKumar-el7ob 3 роки тому +5

      16:22 smaller than equal to is not ok!!
      only smaller than will be ok striver.
      i don't know why anyone didn't point this out.

    • @pranayjain._
      @pranayjain._ Рік тому

      @@PrinceKumar-el7ob It would work. Try some test cases.

    • @artofwrick
      @artofwrick 10 місяців тому

      The best explanation on sliding window

  • @alammahtab08
    @alammahtab08 2 місяці тому +4

    Sliding Window Approach with Monotonic Queue
    The idea is to keep the maximum number in the sliding window at the front of the Deque and the possible maximum numbers at the rear end (last) of the queue. The Deque would have numbers sorted in descending order, front having the maximum number and rear would have the smallest in the current window.
    As we iterate over the array if num[i] is greater than the smallest number of current window than we start removing the numbers as long as num[i] is greater than number in the window.
    Also we add the index of current number in Deque as this number could be possible maximum as the window slides to the right.
    We could have tried to use Stack or PriorityQueue to keep track of maximum in the current window, but we don't only need to track maximum number in the current window but also other numbers (possible maximum) which are less than maximum number in the current window. Because as we move to the next window, these possible maximum numbers might become the maximum number in that window.
    Choosing the right Data Structure : Double Ended Queue (Deque)
    If we use Stack, we can only get access to the top element, for accessing other elements we would have to pop the elements from the stack and would have to push it back to stack.
    Similarly if we use PriorityQueue we can only get access to the min or max element which is at the top of heap, for accessing other elements we would have to remove elements from the heap and would have to push it back to heap.
    A Double ended Queue allows us to perform operation on both the ends of the data structure and we can easily access the elements in Deque. We could have used Doubly Linked List as well but the problem is, it lacks the ease of access to perform operation or access elements from both the front and rear end. In Java Deque gives us methods e.g. addFirst(), addLast(), removeFirst(), removeLast(), peekFirst(), peekLast() to easily access the front/rear element and also start traversal from the front or rear.
    Important Points :
    We store the index i in Deque and not num[i], this is because we also have to remove numbers from the Deque as window slides to the right. We can check if index is out of current window we remove the number.
    For given window of K, remember we don't try to store k elements in the Deque, rather we just need to keep the maximum number at the front of Deque and add the current number at the rear end of Deque. And when we remove element from Deque we start from the rear end of Deque.

  • @priyanshityagi8313
    @priyanshityagi8313 2 роки тому +86

    This explanation literally made me overcome my fear of stacks and queues. Thank you so much!

    • @ayushrawat7951
      @ayushrawat7951 2 роки тому

      Ya exactly..... I also have fear of stack and queue.. Even though they are quite easy to understand.

    • @purushottam108
      @purushottam108 5 місяців тому

      How one question can over come your fear? 🤔🤔🤔🤔

  • @zetro6311
    @zetro6311 2 роки тому +102

    I got this question in a Microsoft interview for SDE 1

    • @kingmaker9082
      @kingmaker9082 2 роки тому

      Is it offcampus or oncampus

    • @zetro6311
      @zetro6311 2 роки тому

      @@kingmaker9082 Off campus

    • @kingmaker9082
      @kingmaker9082 2 роки тому +1

      @@zetro6311 from where u applied for Microsoft or have u got any referral? Plz guide me...btw what is the result of interview bro?

    • @vinyass3733
      @vinyass3733 2 роки тому

      @@kingmaker9082 hello bro? which batch are you?

    • @kingmaker9082
      @kingmaker9082 2 роки тому

      @@vinyass3733 23 batch

  • @parthsalat
    @parthsalat 2 роки тому +11

    I couldn't understand this problem's solution even after reading several leetcode discuss posts. However, I understood this completely at once after watching your video! Thanks!

  • @harigs72
    @harigs72 Місяць тому +1

    I did it by myself.i have been following one coding sheet where i have solved all queue problems (expect one problem and i was able to come up with optimal solution)by myself include one cache problem (Degin pattern)as well .i solve sliding window problem i have cross 4 problem and i have solved 4 problem bu myself.including this one ..i have learnt alot from you ..your teaching style is literally nice . thankyou for work ...🎉❤ Keep doing
    In the problem what i did was
    10:36 instead of checking from back first check peek
    If peek

  • @harshexploring4922
    @harshexploring4922 2 роки тому +12

    kudos to your patience while explaining sir.The way of you instruct the solution to the problem was quite appealing, unlike some other youtubers who just write the code in rush without explaining properly.
    Thanks again

    • @coolmishrag8622
      @coolmishrag8622 9 місяців тому +2

      bro getting harsh with apna collegeg

  • @spardha-yug
    @spardha-yug 2 роки тому +2

    THank you bro.
    Brute force+Optimized+code explanation---->complete video.
    Thanks a ton.

  • @koushalsharma7041
    @koushalsharma7041 2 роки тому +6

    It is always challenging as well as fun to learn the optimal solution. But, your explanation helps a lot to understand it better.

  • @nayan_CSE
    @nayan_CSE Рік тому +1

    What a explanation 😯...I think this is the best video of window problem in UA-cam... Thank you so much for this great video....

  • @deepikasrivastava3040
    @deepikasrivastava3040 3 роки тому +4

    Best Explanation. Thank you so much. Finally understood the use of deque for this problem.

  • @shashank_0807
    @shashank_0807 4 місяці тому +3

    Much better explanation than in the new playlist !

  • @AbhishekKumar-hh8xc
    @AbhishekKumar-hh8xc 2 роки тому +2

    Good explanation. That's an art which is rare. Every one knows the steps and code and solution, But very few know the explanation and intution

  • @patelchintu6492
    @patelchintu6492 3 роки тому +34

    Waiting for tree series :)

  • @pb_yt992
    @pb_yt992 3 роки тому +5

    Such a Nice Explanation even a beginner can understand. Thanks a lot

  • @raghav5354
    @raghav5354 Рік тому +5

    I don’t get the intuition that whenever we remove leftmost index from our window to go to the next window, why the left most index will also be the left most element in the deque (so we just remove the first element from our deque). In my thinking, I should loop through the deque to find the index to remove for every window.

    • @pratikroy710
      @pratikroy710 Місяць тому

      The deque always contains elements in non-increasing order. In other words, deque head always be the greatest element of the window. Thus, when we from move from window [i, i+k-1] to [i+1, i+k], we only need to check if arr[i] (element getting ejected from the window) is at the head or not. It will always be at head if it is present in the deque while it is being ejected.
      Think like this, if there is an element at index j in the window [i, i+k-1] where arr[j]>arr[i], then while inserting j in the deque i would have been removed. Thus if index i is being ejected, then i could only present in the deque only at head.

  • @rajeshg3570
    @rajeshg3570 2 роки тому +1

    Can't find a better explanation than this for a hard problem.. simple love it

  • @juanceja899
    @juanceja899 2 роки тому

    I just had an interview with Google today and this was the algorithm I was given. That's why I'm here Haha. I was able to do it, but I took a different approach.

  • @stith_pragya
    @stith_pragya 8 місяців тому +1

    UNDERSTOOD..........Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

  • @aryanchauhan8066
    @aryanchauhan8066 3 роки тому +3

    Very good explaination , though i have to see it 2 times to completely understand the concept👍

  • @thatbadguy2899
    @thatbadguy2899 3 роки тому +25

    Please increase the frequency of uploads as this is PLACEMENT SEASON

  • @abhishekkmandal
    @abhishekkmandal 3 роки тому +9

    at 3:48 , deque should be Double ended queues I guess and not doubly linked list , btw nice explanation :)

    • @alokesh985
      @alokesh985 3 роки тому +3

      I think he meant that double-ended queues are typically implemented using doubly linked lists

    • @harshexploring4922
      @harshexploring4922 2 роки тому

      @@alokesh985 if i am not wrong in doubly linked list one can access,insert and pop elements at any position but in deque one can do it only at front and back

  • @AyushGupta-kp9xf
    @AyushGupta-kp9xf 3 роки тому +2

    Thanks man I was doubtful about the On complexity. your explanation cleared it :)

  • @aryanchauhan8897
    @aryanchauhan8897 3 роки тому +8

    Very great explanation. Thank you bhaiya for helping out the students but I have one suggestion pls upload videos on regular basis. I know u are very busy but it will be helpful for students who are appearing in this placement season. We have found the solution of dse sheet from anywhere but the video explanation of yours is very helpful to remember the concepts and do similar type questions on particular algorithms.

  • @lifegood6401
    @lifegood6401 3 роки тому +11

    Waiting for tree series eagerly.
    Placement already started in college, and tree , dp, strings remaining from the sheet

  • @manask8116
    @manask8116 Рік тому

    you can do by using a multiset as well , it takes nlogn but its very simple to write the code

  • @aadityaupadhyay6264
    @aadityaupadhyay6264 3 роки тому +3

    That definitely not at 5:15 reminds me of Dhoni xD.

  • @rishurana9655
    @rishurana9655 2 роки тому +2

    This question can also be solve using heap

  • @AlokKumar-or8jz
    @AlokKumar-or8jz Рік тому +2

    easiest solution by naiveApproach
    vector maxSlidingWindow(vector arr,int k){//TLE
    vector ans;
    int n= arr.size();
    for (int i = 0; i < n-k+1; i++)
    {
    ans.push_back(*max_element(arr.begin()+i,arr.begin()+i+k)); // T.C = O(n) max_element
    }
    return ans;


    }

  • @shubham7668
    @shubham7668 2 роки тому +18

    Respect for Aditya verma increased after this lecture 🙇‍♀️🙇‍♀️
    I thought Raj Bhaiya would break the record of his explanation, but he is still unbeatable.

  • @sushantchoudhary444
    @sushantchoudhary444 Рік тому +1

    you are amazing God bless you. I wanna become like you one day

  • @Luk3Stein
    @Luk3Stein Рік тому

    Godly explanation. Suddenly, this problem does not look Leetcode Hard level

  • @kotapatiswaraj06
    @kotapatiswaraj06 Рік тому

    Great Explanation ! Thanks for the free quality content

  • @afaqueahmad7117
    @afaqueahmad7117 Рік тому

    Such an easy explanation, you make it look simple, love it!

  • @rohandevaki4349
    @rohandevaki4349 2 роки тому +2

    how is i-k the outbound element? at 16:02 ?

  • @HARSHAVARDHANE-r1g
    @HARSHAVARDHANE-r1g 11 місяців тому

    the flow of teaching is amazing bor

  • @bharatmehta30
    @bharatmehta30 2 роки тому

    dude!! your explanation is amazing.

  • @oqant0424
    @oqant0424 2 роки тому

    what an Explanation...........hats off ✌✌

  • @biswaranjanbarik4052
    @biswaranjanbarik4052 2 роки тому

    Ur explanation is so awesome.. It's really helpful to us..🙏
    can you plzz upload the video of 862. Leeetcode problem Shortest Subarray with Sum at Least K.🙏🙏
    please sir please I'm really stuck in this prblm.

  • @anandyadav_
    @anandyadav_ 3 роки тому

    I just like every video of yours becuz your's are really gona help.

  • @sujalgupta6100
    @sujalgupta6100 2 роки тому

    this was very hard for me . thanks for such a good explanation.

  • @neerajgarg9096
    @neerajgarg9096 2 роки тому +2

    *Brute force*
    class Solution {
    public:
    vector maxSlidingWindow(vector& nums, int k) {
    vectorans;
    int n = nums.size();
    for(int i=0; i

  • @paragroy5359
    @paragroy5359 2 роки тому

    Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.

  • @kidvschild7240
    @kidvschild7240 2 роки тому +1

    Great brother 👌👌 keep it up 👆

  • @khumukchamsonam4471
    @khumukchamsonam4471 3 роки тому +3

    great explaination as always.... waiting for more videos

  • @rishabhyadav4994
    @rishabhyadav4994 3 роки тому +3

    This can also be solved using multiset, can we use multiset in the interview bhaiya?

  • @cinime
    @cinime Рік тому

    Understood! Amazing explanation as always, thank you very much!!

  • @jaydalsaniya6986
    @jaydalsaniya6986 2 роки тому

    Worst case occurs when k = 1 , Inserting all N element and N-1 elements will be removed. This is because for each array element two operation DELETION -> INSERTION IS PERFORMED .

  • @helderfilho4724
    @helderfilho4724 Рік тому

    Thank You very much! You explain very well.

  • @Satya-g5t
    @Satya-g5t 3 місяці тому +1

    good explanation, thank you.

  • @poorvaparande5933
    @poorvaparande5933 2 роки тому +1

    Thanks a lot! this was super helpful :)

  • @sohailshaik9
    @sohailshaik9 2 роки тому

    had to watch 2 times to understand this but it was beautiful. thanks

  • @_dion_
    @_dion_ 10 місяців тому

    the best explanation on yt.

  • @vedanshbhardwaj6548
    @vedanshbhardwaj6548 3 роки тому +4

    Hello Striver, new here, can you tell whether you are covering only this SDE sheet here on any other topics too ? anyone ?

    • @takeUforward
      @takeUforward  3 роки тому +6

      I am brining in series shortly..

  • @anutoshghosh7893
    @anutoshghosh7893 10 місяців тому

    Is there any algorithm related to next greatest element or next smallest element, like how to devise algorithms for these type of problems, how to know we need a deque in this case as we do operations on both sides here?

    • @ManishKumar-qx1kh
      @ManishKumar-qx1kh 2 місяці тому +1

      There's another solution of this using next greater element approach, saw it here ua-cam.com/video/tCVOQX3lWeI/v-deo.html
      as i was also thinking of applying nge algorithm.

  • @theresilientpianist7114
    @theresilientpianist7114 11 місяців тому

    ❣❣you are a legend🙏🙏

  • @s41nt2
    @s41nt2 Рік тому

    Genius guy🙌🙌

  • @nani4027
    @nani4027 3 роки тому +1

    Nice explanation bro!

  • @hussainkanchwala968
    @hussainkanchwala968 10 місяців тому

    very clear explanation, thanks

  • @1qwertyuiop1000
    @1qwertyuiop1000 Рік тому

    How about using Max Heap with size K.. time complexity will be NLogN i guess.. Space complexity will be O(K)

  • @prachigupta9713
    @prachigupta9713 2 роки тому

    Thankyou So much for such excellent explaination

  • @kapilpatel9379
    @kapilpatel9379 2 роки тому

    Could not understand completely, but will come back

  • @asp1859
    @asp1859 Рік тому

    Is the time complexity , really O(n) here ??.... because, if we take example, 6,4,5,3,2 with window size k =3, then once the greatest element 6 is removed, the next greatest element that is 5 should be placed at top, and for doing that worst case, there will be (k-1) comparisons. Anybody please correct me if I am wrong .

  • @freshcontent3729
    @freshcontent3729 3 роки тому +1

    bhaiya please bring more videos fast fast .. placements are starting!!

  • @gandhijainamgunvantkumar6783
    @gandhijainamgunvantkumar6783 2 роки тому

    Bhaiya please make a video on the question: Find maximum of minimum for all the window sizes.

  • @anirudhvermarr
    @anirudhvermarr 9 місяців тому

    Simply, thank you!

  • @biswaranjanbarik4052
    @biswaranjanbarik4052 2 роки тому

    Ur explanation is so awesome.. It's really helpful to us..🙏
    can you please upload the video of 862. Leetcode problem Shortest subarray with Sum at Least K.🙏🙏
    please sir please I'm really stuck in this problem.

  • @mugambo5505
    @mugambo5505 2 роки тому

    awesome explanation bro.
    all doubts gone

  • @vrajsoni7610
    @vrajsoni7610 3 роки тому

    Was waiting for a video on this specific question, thanks a lot

  • @vuyyurishanmukhaabhinavvar4096
    @vuyyurishanmukhaabhinavvar4096 3 роки тому +5

    Bhai when your course starts in unacademy pls update waiting for your course

  • @_-6912
    @_-6912 3 роки тому +1

    I understood the solution!

  • @ujjawaldewangan8345
    @ujjawaldewangan8345 3 роки тому

    It is necessary because no one teach us like you

  • @abhityagi9807
    @abhityagi9807 Рік тому

    14:22 ye time complexity O(n-k)+O(k) ni honi chahiye be because hum ans vector bhi to store kar rahe hai plz clear my doubt

  • @shalinig1253
    @shalinig1253 4 місяці тому

    Great Explanation!

  • @millionaires1
    @millionaires1 2 роки тому

    Very good explanation, thank you bro

  • @sahilsingh5695
    @sahilsingh5695 Рік тому

    not able to understand the lst part of the i>-=k-1 onwards part

  • @earninghere7442
    @earninghere7442 5 місяців тому +1

    Python simple one
    x=[1,3,-1,-3,5,3,6,7]
    k=3
    y=[]
    for i in range(len(x)-2):
    y.append(max(x[i:i+k]))
    print(y)

  • @ketanahuja8939
    @ketanahuja8939 3 роки тому +1

    Great Explanation

  • @nikhilrana2680
    @nikhilrana2680 3 роки тому +1

    Bhaiya...shukr h..aap aaye yahan...😅😂bda acha lga....

    • @takeUforward
      @takeUforward  3 роки тому +3

      Haan bhai, Insta follow karoge toh pata hoga na 😴

    • @nikhilrana2680
      @nikhilrana2680 3 роки тому

      Bhaiya krta hu apko follow but...2-3 din se insta nhi chalaya😂😅

    • @nikhilrana2680
      @nikhilrana2680 3 роки тому

      Bhaiya ek cheex aur, voh apki trees ki series kb tk ayegi...mein 1 year mein hu..dsa shuru kr dia h...trees padna h aapse, plzz bhaiya jldi lao....😄🥰

  • @1murkeybadmayn
    @1murkeybadmayn Рік тому

    The part that confuses me is dq.empty() or dq.front(), i thought they return a value at the index not the index itself. So how is it used here that it is checking the index and not the value? I am so confused.

  • @171-supratiksantra5
    @171-supratiksantra5 3 роки тому

    I got this question in one interview round and also in the written round

  • @krishnavamsichinnapareddy
    @krishnavamsichinnapareddy Рік тому

    Nice explanation 👍

  • @rohankumar393
    @rohankumar393 3 роки тому +1

    Please add heap questions in SDE sheet.

  • @yashsaini9494
    @yashsaini9494 2 роки тому

    This person is gifted

  • @perumallayaswanth83
    @perumallayaswanth83 3 роки тому +1

    Bro can u please make a video on how to deal with large numbers and what exactly 10^9+7.

  • @rushikeshdeshmukhmarathibo7465

    Understood bhaiya ❤

  • @siddhantraut4773
    @siddhantraut4773 3 роки тому

    Great explanation ❤️❤️

  • @naveengarg7435
    @naveengarg7435 2 роки тому +2

    directly jumped to solution,
    Intution is missing... :(

  • @shristisrivastava7054
    @shristisrivastava7054 Рік тому

    Huge fan of your videos

  • @herculean6748
    @herculean6748 Рік тому

    we can do this using queue also, why queue is not used and deque is used?

  • @KittyInCali
    @KittyInCali 4 місяці тому

    thanks for great explanation

  • @shubham6215
    @shubham6215 3 роки тому

    Thank you bhaiya ❤️👍

  • @RamKrishna-ou6li
    @RamKrishna-ou6li 3 роки тому

    good explanation thank you so much

  • @itz_me_imraan02
    @itz_me_imraan02 Рік тому

    I solved it using segment tree

  • @amansamal8233
    @amansamal8233 3 роки тому +1

    understoooddddddd🥺❤

  • @shobhitmishra739
    @shobhitmishra739 3 роки тому +1

    can we use max heap??

  • @StudyEmail-p9u
    @StudyEmail-p9u 11 місяців тому +1

    Thank You!!

  • @adeebarif3791
    @adeebarif3791 3 роки тому

    👍 Great Bhaiya

  • @subhankarkanrar9494
    @subhankarkanrar9494 5 місяців тому +1

    Love❤😊

  • @sudiksha586
    @sudiksha586 Рік тому

    thank you striver!