# Find maximum of all subarrays of size k

Problem

Given an array of size n and an integer k, we need to find the maximum for each contiguous subarray of size k.

###### Sliding window using Deque

We’ll discuss a solution using the sliding window approach, which allows us to solve the problem with a time complexity of O(n). We’ll be using a Double-ended queue (Deque) to solve this problem.

The sliding window approach involves maintaining a window of elements as we traverse the array. In this problem, we’ll use a deque (double-ended queue) to efficiently find the maximum within the current window. The deque will store indices of array elements in a way that ensures the maximum element is always at the front.

Sliding window approach is also discussed in these posts:

###### Example
Input: array (nums) = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
###### Approach
1. Initialise an empty deque using the first k elements of the array.
2. Iterate through the array from index k to the end (n-1).
• Remove elements from the front of the deque that are outside the current window.
• Next, remove the elements from the back of the deque that are lesser than the current element
• The front of the deque now contains the maximum element index for the current window. Add the current index to the deque.
• Add the maximum element to the result for the current window.
3. Return the result array (ans) containing maximum elements for each window of size k.
###### Pseudocode
1. Create an empty deque (dq) to store indices of the array.
2. Process first k elements of the array to initialise deque (initialise_deque).
3. for i = k to n-1 (iterate through array):
4.   while dq.front() <= i-k:
dq.pop_front()
5.   while nums[i] > nums[dq.back]:
dq.pop_back()
5.   dq.push_back(i)

initialise_deque (dq, nums):
for i = 0 to k-1:
(remove elements from the back of the deque until the current element is greater than the queue's back element)
while nums[i] > nums[dq.back]:
dq.pop_back()
dq.push_back(i)

Code Implementation

//
//  main.cpp
//  Maximum of all Subarrays of Size k
//
//  Created by Himanshu on 10/01/22.
//

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
vector<int> result;
deque<int> dq;

// Process the first k elements
for (int i = 0; i < k; i++) {

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

dq.push_back(i);
}

// Iterate through the array from index k to the end
for (int i = k; i < nums.size(); i++) {

// Add the maximum element of the curent window
// to the result
result.push_back(nums[dq.front()]);

// Remove elements from the front of the deque
// that are outside the current window
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}

// Remove elements from the back until the current element
// is greater than the element at the back
while (!dq.empty() && nums[i] > nums[dq.back()]) {
dq.pop_back();
}

// Add the current index to the deque
dq.push_back(i);
}

// Add the maximum element for the last window
result.push_back(nums[dq.front()]);

return result;
}

int main() {
vector<int> nums = {1, 3, 2, -3, 5, -2, 6, 7};
int k = 3;

vector<int> result = maxSlidingWindow(nums, k);

// Print the result
for (int num : result) {
cout << num << " ";
}

return 0;
}


Output

3 3 5 5 6 7

Time complexity: O(n)
Auxiliary space: O(k)