Maximum Number in Sliding Window

Maximum in Sliding Window Algorithm:

Given an input array and a window size, we need to output the maximum element each time in the window, sliding the window by one element every time.

For eg:
input:   {1, 3, -1, -3, 5, 3, 6, 7};
output: {3, 3, 5, 5, 6, 7}

Points to remember:

1. We always maintain the largest element index at the start of the deQueue.
2. When we are inserting a new element index into the Deque, do the following:
- Compare the inserting element with the queue elements from its end. If anything is lower than the inserting element, then remove it.
- Now check the validity of indices from starting of the queue. If any element is out of current window range, then remove it from queue.

Algorithm:

1. Take the input array and window size
2. initialize output array with a size of (input.length-window size)
3. Create a Double Ended Queue - Dequeue (size will be maximum of window size)

4. Now as an initial step, fill the Dequeue as below.
for(int i=0; i<window.size; i++) {
Do the following recursively, if the queue is not empty.
If the element to be inserted is greater than the last element of the DeQueue, then delete the last element of the Dequeue

Now insert the index of the element to be inserted, i.e "i" at the end of the queue.
}

5. Now follow the below steps for remaining elements:
for(int i=window.size; i<input.size; i++) {
a) Get the first element(i.e. index) of the queue and insert it to output array at (i-w) position
b) Compare the inserting element with the queue elements from the end. If any queue is element less than inserting element, then delete it.
c) Check the index validity of queue elements from its start. If any element is out of the window range, then delete it.
d) insert the current element to the queue.
}

6. Get the first element from the queue and insert it to the output array.


Java Code:

import java.util.Arrays;

class MaxSlidingWindow {
        static public int[] maxSlidingWindow(int[] ar, int w) {
                int n = ar.length;
                int[] out = new int[n-w+1];

                DeQueue queue = new DeQueue();

                //prepare initial window
                for(int i=0; i<w; i++) {
                        while( !queue.isEmpty() && ar[i] > ar[queue.getLast()])
                                queue.deleteLast();

                        queue.insertLast(i);
                }

                for(int i=w; i<ar.length; i++) {
                        out[i-w] = ar[queue.getFirst()];

                        //clear the queue wrt the element to be inserted
                        while(!queue.isEmpty() && ar[i] > ar[queue.getLast()])
                                queue.deleteLast();

                        //clear the queue wrt the out of indices
                        while(!queue.isEmpty() && queue.getFirst() <= (i-w))
                                queue.deleteFirst();

                        queue.insertLast(i);
                }

                out[n-w] = ar[queue.getFirst()];

                return out;
        }

        static public void main(String[] args) {
                int[] ar = {1, 3, -1, -3, 5, 3, 6, 7};
                int[] out = maxSlidingWindow(ar, 3);

                System.out.println(Arrays.toString(ar));
                System.out.println(Arrays.toString(out));
        }
}


eg:
i/p: {1, 3, -1, -3, 5, 3, 3, 6, 7}
w=3
Queue is empty

Filling the window initially:
1. i=0
Since queue is empty, just insert this index into Queue.
Queue: {0}

2. i=1
ar[i] > ar[queue.getLast()] ==> ar[1] > ar[0] ==> 3 > 1 ==> correct
remove the ar[queue.getLast()] from Queue. Now the Queue is empty.

insert current element index to queue.
Queue: {1}

3. i=2
since ar[i] > ar[queue.getLast()] ==> ar[2] > ar[1] ==> -1 > 3 ==> is wrong
So dont do anything

insert current element index to queue.
Queue: {1, 2}


Starting the actual process:
1. i=3
insert the queue.getFirst() to output array:
==> output={3, 0, 0, 0, 0, 0}

ar[i] > ar[queue.getLast()] ==> ar[3] > ar[2] ==> -3 > -1 ==> is wrong

valid window range: [i-w+1 to i] ==> [1, 3]
all queue indices are valid

insert current element index to queue.
Queue: {1, 2, 3}

2. i=4
insert the queue.getFirst() to output array:
==> output={3, 3, 0, 0, 0, 0}

ar[i] > ar[queue.getLast()] ==> ar[4] > ar[3] ==> 5 > -3 ==> correct
remove the ar[queue.getLast()] from Queue:
Queue ==> {1, 2}

again: ar[i] > ar[queue.getLast()] ==> ar[4] > ar[2] ==> 5 > -1 ==> correct
remove the ar[queue.getLast()] from Queue:
Queue ==> {1}

again: ar[i] > ar[queue.getLast()] ==> ar[4] > ar[1] ==> 5 > 3 ==> correct
remove the ar[queue.getLast()] from Queue:
Queue ==> {}

Check the validity of queue indices from starting: valid window range: [2, 4]
Since queue is empty. dont do anything.

insert current element index to queue.
Queue: {4}

3. i=5
insert the queue.getFirst() to output array:
==> output = {3, 3, 5, 0, 0, 0}

ar[i] > ar[queue.getLast()] ==> ar[5] > ar[4] ==> 3 > 5 ==> is wrong.
dont do anything

valid window range: [3, 5]
queue indices are valid.

insert the current index to queue:
Queue: {4, 5}

...