Given an array and integer k find maximum value in each subarray of size k

Question

I'm struggling with a question on hackerrank deque-stl. I have implemented an algorithm which finds the maximum element in the windows and stores its index, then use this index of the maximum element in the previous window to find the maximum element in the next window only if the index of maximum element lies between the indexes of the next window. Using this algorithm and suggestions mentioned in the comments i've implemented this updated algorithm but i'm still getting Wrong Answer Error.

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int m,idx;
void maxinwindow(int arr[], int start, int end)
{
    /*If the index of the maximum element in the previous window
    is between the indexes of next windows then no need to compare 
    elements that were in previous window */
    if(idx>=start)
    {
        if(arr[idx]>=arr[end])
        {
            m=arr[idx];
        }
        else
        {
            m=arr[end];
            idx=end;
        }
    }
    else
    {
        if(arr[start]>=arr[start+1])
            m=arr[start];
        else
            m=arr[start+1];
        for(int k=start+2;k<=end;k++)
        {
            if(arr[k]>=m)
            {
                m=arr[k];
                idx=k;
            }
        }
    }
}
int main()
{
    int arr[100000];
    int q;
    cin>>q;
    for(int i=1,size,ws;i<=q;i++)
    {
        m=0;
        cin>>size;  //Array size
        cin>>ws;   //Window Size
        //Entering The Elements In The Array
        for(int j=1;j<=size;j++)
        {
            cin>>arr[j];
        }
        //Boundary Condition i.e. Windows size is equal to 1
        if(ws==1)
        {
            for(int j=1;j<=size;j++)
            {
                cout<<arr[j]<<" ";
            }
        }
        else
        {
            for(int k=1;k<=ws;k++)
            {
                if(arr[k]>=m)
                {
                    m=arr[k];
                    idx=k;
                }
            }
            cout<<m<<" ";
            for(int k=2,j;k<=(size-(ws-1));k++)
            {
                j=(k+(ws-1));
                maxinwindow(arr,k,j);
                cout<<m<<" ";
            }
            cout<<endl;
        }
    }
}

Answer 1

Introduction

To solve this problem efficiently, keep track of elements that can be maximum values within the current or following sliding windows.

Algorithm

In your Hackerrank exercise, you're supposed to use std::deque in order to solve the problem efficiently. So, I would suggest not to diverge from this and solve it using std::deque.

Let's consider an example. Given an array arr = [4, 3, 4, 2, 5] and window k = 3, how to find a maximum value in each subarray of length 3?

1. Go through first 3 elements and keep relevant indices of array elements in the queue.

   Step 1
   arr:     |4| 3 4 2 5
   queue :  |0|
   

   Add an index of the first element because the queue is empty.

   Step 2
   arr:     |4 3| 4 2 5
   queue :  |0 1|
   

   Add an index 1 but keep 0 as arr[0] > arr[1]. But why to keep 1 then? Even though arr11] is smaller in this sliding window it can be the largest in another one without arr[0].

   Step 3
   arr:     |4 3 4| 2 5
   queue :  |  2  |
   

   In the last step, we kept only 2 in the queue. Why? Because arr[2] wasn't smaller than
   arr[0] or arr[1]. So, it didn't make sense to keep those indices as the maximum value in this subarray would still be arr[2].

   Since the first sliding window is complete, print arr[queue.front()]. The first element of the queue corresponds to an index of the maximum element in the subarray.

2. Once first 3 elements are processed, on each iteration the sliding window starts moving to the right:

   arr:      4 |3 4 2| 5
   queue :     | 2 3 | 
   

   Print arr[2] as the maximum value. Again, the first element of the queue corresponds to an index of the maximum element in the subarray. 3 is kept in the queue because potentially it can correspond to an index of the maximum value in the next sliding windows.

   arr:      4 3 |4 2 5|
   queue :       |  4  |
   

   Finally, 4 remains the only element, as 2 is popped out anyways (it doesn't belong to the current window) and arr[4] >= arr[3] so it doesn't make sense to keep it.

To summarise, here are the steps of an algorithm:

1. For the first k elements of an array, store indices of possible max subarray elements in a queue. On each i-th iteration, keep popping out elements from the queue if their mapped values don't exceed arr[i] and then push arr[i] into the queue.

   In the end, the first element of the queue contains an index of the max value.

2. For the remaining array elements, on each iteration i, pop out the first element front only if it doesn't belong to the current sliding window anymore - i - front == k. Then, as before, pop out indices which mapped values don't exceed arr[i] and afterwards push arr[i] into the queue (again, at the end of each iteration, the queue contains an index of the max value).

Hopefully, now it's clear how this idea can be implemented. The time complexity of the solution is O(n). The space complexity is also O(n).

Code

#include <algorithm>
#include <iostream>
#include <deque> 

void printKMax(int arr[], int n, int k){
    std::deque<int> queue;

    for (int i = 0; i < k; i++) {
        while (!queue.empty() && arr[queue.back()] <= arr[i]) {
            queue.pop_back();
        }

        queue.push_back(i);
    } 

    for (int i = k; i < n; i++) {
        std::cout << arr[queue.front()] << " ";

        // an element with index queue.front() no longer belong to ths window
        if (i - queue.front() == k) {
            queue.pop_front();  
        }

        // pop all elements that don't exceed arr[i] as they're no longer useful
        while (!queue.empty() && arr[queue.back()] <= arr[i]) {
            queue.pop_back();
        }  

        queue.push_back(i);
    }

    std::cout << arr[queue.front()] << "\n";
}