Given an array, find the maximum of all subarrays of size k

Problem: Given an array and an integer k, find the maximum for each and every contiguous sub array of size k.

For example:

Input: arr[] = {9, 6, 11, 8, 10, 5, 14, 13, 93, 14}
Output: 11 11 11 14 14 93 93

In above example: 11 is the largest element in the first, second and third 
sub arrays - {9,6,11,8}, {6,11,8,10} and {11,8,10,5}. 14 is the largest element 
for fourth and fifth sub-array and 93 is the largest element for remaining sub-arrays.

Method 1: The naive approach is to use two nested loops. In the outer loop, take all sub arrays of size k. In the inner loop, get the maximum of the current sub array.

void K_Max(int arr[], int n, int k)
{
    int max;

    for (int i = 0; i <= n-k; i++)
    {
        max = arr[i];
        for (int j = 1; j < k; j++)
        {
            if (arr[i+j] > max)
               max = arr[i+j];
        }
        cout<<max<<" ";
    }
    cout<<"\n";
}

Time Complexity: O(n*k)

Method 2: We can solve this problen in O(n) using a Dequeue data structure. Dequeue dQ of capacity k, stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain dQ to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the dQ is the largest and element at rear of dQ is the smallest of current window.

#include <bits/stdc++.h>
using namespace std;

/* function to print maximum of all subarray of size k */
void kMax(int arr[], int n, int k)
{
    /* here we are using stl to create a DeQueue */
    deque<int> dQ;
    int i;

    /* processing first k elements of array */
    for(i = 0; i < k; i++)
    {
        /* removing the previous elements that are smaller than 
           current elements */
        while(!dQ.empty() && arr[i]>=arr[dQ.back()])
            dQ.pop_back();

        /* adding new element to rear of queue */
        dQ.push_back(i);
    }

    /* processing rest n-k elements of array */
    for( ; i < n; i++)
    {
        /* element at the front of the queue is the largest element of
           previous window */
        cout<<arr[dQ.front()]<<" ";

        /* remove the elements that are out of this window */
        while(!dQ.empty() && dQ.front()<=i-k)
            dQ.pop_front();

        /* removing the previous elements that are smaller than 
           current elements */
        while(!dQ.empty() && arr[i]>=arr[dQ.back()])
            dQ.pop_back();

        /* adding new element to rear of queue */
        dQ.push_back(i);       
    }

    /* maximum of last window */
    cout<<arr[dQ.front()]<<endl;
}

/* driver function */
int main() 
{
    int arr[] =  {9,6,11,8,10,5,14,13,93,14};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;

    kMax(arr, n, k);

    return 0;
}

Output:

11 11 11 14 14 93 93

Time Complexity: O(n) and Space Complexity: O(k)

Method 3: We can also solve this problem using max Heap os size k. The elements at top of max Heap is always the greatest. Below is C++ implementation of idea.

#include <bits/stdc++.h>
using namespace std;

/* function to print maximum of all subarray of size k */
void kMax(int arr[], int n, int k)
{
    /* we use priority_queue to implement max Heap. We store the element
       and its index as pair in priority_queue */
    priority_queue< pair<int, int> > pq;

    /* processing first k - 1 elements of array */
    for(int i 0; i < k-1)
    {
        pq.push(mp(arr[i], i));
    }

    /* processing first rest elements of array */
    for( int i = k - 1; i < n; i++)
    {
        pq.push(mp(arr[i], i));

        /* removing the previous elements that are out of current window */
        while(pq.top().se <= (i - k))
            pq.pop();

        /* we know in max Heap, top element is always maximum */
        cout<<pq.top().fi<<" ";
    }
    
    cout<<" ";

}

/* driver function */
int main()
{
    int arr[] =  {9,6,11,8,10,5,14,13,93,14};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;

    kMax(arr, n, k);

    return 0;
}

Output:

11 11 11 14 14 93 93

Time Complexity: O(n*logk) and Space Complexity: O(k)