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:

• Find maximum sum of contiguous subarray of size k
• Find number of subarrays with given sum (Non-negative numbers)

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)