Queue: Maximum of all subarrays of size K

Problem Statement:

You are given an array, and integer k.

You need to find the max value for each contiguous sub array of size k.

Output should be subarray of maximum values.

Example:

Input: arr = [1, 2, 3, 4, 1, 2], k = 3

Output: 
[6, 9, 9, 9]

[1, 2, 3] max = 6
[2, 3, 4] max = 9
[3, 4, 1] max = 9
[4, 1, 2] max = 9

Solution 1: Brute force approac

In this approach, run 2 nested loops.

Outer loop will start from the starting point of length k.

Inner loop will run from the starting index to index+k.

Then print the maximum element among the k elements.

Time Complexity: O(n * k)
Space Complexity: O(1)

Solution 2: dequeue approach

Solution is very simple.

we will use dequeue to solve the problem.

Iterate through the array, remove the element form the front of dequeue of its out of the current window.

Remove the element from back of the dequeue if the element is less than nums[i]

Time Complexity: O(n)
Space Complexity: O(k), k is the window size

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <deque>

using namespace std;

vector<int> solution_1(vector<int>& arr, int k) 
{
    int n = arr.size();

    vector<int> res;
  
    for (int i = 0; i <= n - k; i++) 
    {
      
        int max = arr[i];
        for (int j = 1; j < k; j++) 
        {
            if (arr[i + j] > max)
                max = arr[i + j];
        }
        res.push_back(max);
    }
  
    return res;
}

vector<int> solution_2(vector<int>& nums, int k) 
{

    deque<int> dq;
    vector<int> res;

    for (int i = 0; i < nums.size(); i++) 
    {
        if (!dq.empty() && dq.front() == (i - k)) 
        {
            dq.pop_front();
        }

        while (!dq.empty() && nums[dq.back()] < nums[i]) 
        {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= (k - 1)) 
        {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

int main() 
{
    vector<int> arr = { 1, 1, 2, 3, 4, 1, 4, 5, 6, 7};
    int k = 3;
    vector<int> res = solution_1(arr, k);
    for (int val : res) 
    {
        cout << val << " ";
    }
    cout<<endl;
    res = solution_2(arr, k);
    for (int val : res) 
    {
        cout << val << " ";
    }
    return 0;
}

Output

2 3 4 4 4 5 6 7 
2 3 4 4 4 5 6 7