Finding maximum for every window of size k in an array

You have heard about doing it in O(n) using dequeue.

Well that is a well known algorithm for this question to do in O(n).

The method i am telling is quite simple and has time complexity O(n).

Your Sample Input:
n=10 , W = 3

10 3
1 -2 5 6 0 9 8 -1 2 0

Answer = 5 6 6 9 9 9 8 2

Concept: Dynamic Programming

Algorithm:

1. N is number of elements in an array and W is window size. So, Window number = N-W+1

2. Now divide array into blocks of W starting from index 1.

   Here divide into blocks of size 'W'=3. For your sample input:

   

3. We have divided into blocks because we will calculate maximum in 2 ways A.) by traversing from left to right B.) by traversing from right to left. but how ??

4. Firstly, Traversing from Left to Right. For each element ai in block we will find maximum till that element ai starting from START of Block to END of that block. So here,

   

5. Secondly, Traversing from Right to Left. For each element 'ai' in block we will find maximum till that element 'ai' starting from END of Block to START of that block. So Here,

   

6. Now we have to find maximum for each subarray or window of size 'W'. So, starting from index = 1 to index = N-W+1 .

   max_val[index] = max(RL[index], LR[index+w-1]);

   

     for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5
   

Simliarly, for all index i, (i<=(n-k+1)), value at RL[i] and LR[i+w-1] are compared and maximum among those two is answer for that subarray.

So Final Answer : 5 6 6 9 9 9 8 2

Time Complexity: O(n)

Implementation code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LIM 100001 

using namespace std;

int arr[LIM]; // Input Array
int LR[LIM]; // maximum from Left to Right
int RL[LIM]; // maximum from Right to left
int max_val[LIM]; // number of subarrays(windows) will be n-k+1

int main(){
    int n, w, i, k; // 'n' is number of elements in array
                    // 'w' is Window's Size 
    cin >> n >> w;
         
    k = n - w + 1; // 'K' is number of Windows

    for(i = 1; i <= n; i++)
        cin >> arr[i];

    for(i = 1; i <= n; i++){ // for maximum Left to Right
        if(i % w == 1) // that means START of a block
            LR[i] = arr[i];
        else
            LR[i] = max(LR[i - 1], arr[i]);        
    }

    for(i = n; i >= 1; i--){ // for maximum Right to Left
        if(i == n) // Maybe the last block is not of size 'W'. 
            RL[i] = arr[i]; 
        else if(i % w == 0) // that means END of a block
            RL[i] = arr[i];
        else
            RL[i] = max(RL[i+1], arr[i]);
    }

    for(i = 1; i <= k; i++)    // maximum
        max_val[i] = max(RL[i], LR[i + w - 1]);

    for(i = 1; i <= k ; i++)
        cout << max_val[i] << " ";

    cout << endl;

    return 0;
}  

Running Code Link

---

I'll try to proof: (by @johnchen902)

If k % w != 1 (k is not the begin of a block)

Let k* = The begin of block containing k
ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = max( max( arr[k],  arr[k + 1],  arr[k + 2],  ..., arr[k*]), 
              max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) )
       = max( RL[k], LR[k+w-1] )

Otherwise (k is the begin of a block)

ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = RL[k] = LR[k+w-1]
       = max( RL[k], LR[k+w-1] )

Dynamic programming approach is very neatly explained by Shashank Jain. I would like to explain how to do the same using dequeue. The key is to maintain the max element at the top of the queue(for a window ) and discarding the useless elements and we also need to discard the elements that are out of index of current window.
useless elements = If Current element is greater than the last element of queue than the last element of queue is useless .
Note : We are storing the index in queue not the element itself. It will be more clear from the code itself.
1. If Current element is greater than the last element of queue than the last element of queue is useless . We need to delete that last element. (and keep deleting until the last element of queue is smaller than current element).
2. If if current_index - k >= q.front() that means we are going out of window so we need to delete the element from front of queue.

vector<int> max_sub_deque(vector<int> &A,int k)
{
    deque<int> q;
    for(int i=0;i<k;i++)
    {
        while(!q.empty() && A[i] >= A[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    vector<int> res;
    for(int i=k;i<A.size();i++)
    {
        res.push_back(A[q.front()]);
        while(!q.empty() && A[i] >= A[q.back()] )
            q.pop_back();
        while(!q.empty() && q.front() <= i-k)
            q.pop_front();
        q.push_back(i); 
    }
    res.push_back(A[q.front()]);
    return res;
}

Since each element is enqueued and dequeued atmost 1 time to time complexity is
O(n+n) = O(2n) = O(n).
And the size of queue can not exceed the limit k . so space complexity = O(k).

An O(n) time solution is possible by combining the two classic interview questions:

• Make a stack data-structure (called MaxStack) which supports push, pop and max in O(1) time.
  

  This can be done using two stacks, the second one contains the minimum seen so far.

• Model a queue with a stack.
  

  This can done using two stacks. Enqueues go into one stack, and dequeues come from the other.

For this problem, we basically need a queue, which supports enqueue, dequeue and max in O(1) (amortized) time.

We combine the above two, by modelling a queue with two MaxStacks.

To solve the question, we queue k elements, query the max, dequeue, enqueue k+1 th element, query the max etc. This will give you the max for every k sized sub-array.

I believe there are other solutions too.

1)

I believe the queue idea can be simplified. We maintain a queue and a max for every k. We enqueue a new element, and dequeu all elements which are not greater than the new element.

2) Maintain two new arrays which maintain the running max for each block of k, one array for one direction (left to right/right to left).

3) Use a hammer: Preprocess in O(n) time for range maximum queries.

The 1) solution above might be the most optimal.