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

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";
}