Queues (Maximum element in every window of size k )

#1

sir i m unable to understand the theory of this topc ,literally i have seen the video 3 times ,ans yet unable to understand,plz help me in understanding this

#2

hey @sameeksha
Input : arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output : 3 3 4 5 5 5 6
Explanation:
Maximum of 1, 2, 3 is 3
Maximum of 2, 3, 1 is 3
Maximum of 3, 1, 4 is 4
Maximum of 1, 4, 5 is 5
Maximum of 4, 5, 2 is 5
Maximum of 5, 2, 3 is 5
Maximum of 2, 3, 6 is 6

  • Dry run of the above approach:
    1161×1652 130 KB
  • Algorithm :
    1. Create a deque to store k elements.
    2. Run a loop and insert first k elements in the deque. While inserting the element if the element at the back of the queue is smaller than the current element remove all those elements and then insert the element.
    3. Now, run a loop from k to end of the array.
    4. Print the front element of the array
    5. Remove the element from the front of the queue if they are out of the current window.
    6. Insert the next element in the deque. While inserting the element if the element at the back of the queue is smaller than the current element remove all those elements and then insert the element.
    7. Print the maximum element of the last window.