Sliding window deque

#1

i understood how its working foe the first k elements that is 1,2,3 but how window is moving to next k elements that is 2,3,1 its damn confusing?

#2

@jatinupadhyay786

Input:
n = 9
1 2 3 1 4 5 2 3 6 (elements)
0 1 2 3 4 5 6 7 8 (indices)
k = 3

initially we process the first k elements. The largest element in 0,1,2 is present at ar[2]
so the deque is: 2 _ _

Now, to the second for loop.

i is at k, ie 3. i-k = 0. a[i] = 1
print a[q.front()] so a[2] is printed

  1. none of the elements are from outside the window, so nothing get popped
  2. a[i] is not greater than q.back(), again nothing gets popped
  3. i is added to the queue so the queue becomes 2 3 _

i comes at 4, i-k = 1, a[i]=4
print a[q.front()] so a[3] is printed

  1. none of the elements are from outside the window, so nothing get popped
  2. a[i] (4) is greater than a[q.back()] (1) so we remove the index 3, deque becomes 2 _ _
    again, a[i] (4) is greater than a[q.back()] (3) so we remove the index 2, deque becomes _ _ _
  3. Add i in the deque, so deque becomes 4 _ _

i comes at 5, i-k = 2, a[i] = 5
print a[q.front()] so a[3] is printed

  1. none of the elements are from outside the window, so nothing get popped
  2. a[i] (5) is greater than a[q.back()] (4) so we remove the index 3, deque becomes _ _ _
  3. Add i in the deque, so deque becomes 5 _ _

Similarly you can dry run for the rest of the elements

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.