Cnt understand the algorithm of this question used

#1

cant understand the algorithm

#2

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.