### Sliding Window Maximum Algorithm

Sliding Window Maximum Algorithm (To track the maximum of each subarray of size k)

Problem:- Write an algorithm to track the maximum of each subarray of size k in time complexity O(n) and space complexity O(k), where n is the size of the array and k is size of the window from which you have to find the maximum.

input: ar[] = { 1, 5, 3, 9, 2, 0, 5, 4, 9} Output: 5, 9, 9, 9, 5, 5, 9 Subarrays – max[1, 5, 3]= 5 max[5, 3, 9]= 9 max[3, 9, 2] = 9 max[9, 2, 0]= 9 max[2, 0, 5] = 5 max[0, 5, 4] = 5 max[5, 4, 9] = 9

Solution:-

Simple Approach:- These problem can be solved by using the outer loop to run till ‘n’ and inner loop to run starting from ‘i’ to ‘k’.

But this will take time complexity equal to O(n*k).

Sliding Window Approch:-

We will be using Deque(Double Ended Queue) in which we store the elements first of window ‘k’.

The property of Deque is that the elements in the Deque is automatically becomes sorted and element can be inserted and deleted from both the ends.

Steps:-

1: Firstly, we will create a Deque of size ‘k’ , and insert the elements in it. Deque can have max ‘k’ elements.

As the deque is filled , we will increase the index( i.e we will slide the window) and discard the index of the elements which does not fall in this range.

2:- Deque will only store the index of the elements.

3:- Once the window is created for first ‘k’ elements and then when new index is inserted

3.1 Remove the index which falls outside the window.

3.2 And remove the smaller index elements as these elements will not be needed in the deque because we have to find the maximum of subarray ‘k’.

4:- Output from each window since we have to find the maximum in each slide of length ‘k’;

Time Complexity: O(n), Space Complexity: O(k)

int [] ar = { 1,5, 3, 9, 2, 0, 5, 4, 9} K = 3 Create deque for first k elements int [] ar = { 1, 5, 3, 9, 2, 0, 5, 4, 9}; Deque: Output: __________________________________ int [] ar = {1, 5, 3, 9, 2, 0, 5, 4, 9}; NOTE : we are adding the array index, not elementDeque: 0 Output:__________________________________ int [] ar = { 1,5, 3, 9, 2, 0, 5, 4, 9}; 5>1, remove 1 from deque and add 5’s index at the endDeque: 1 Output:__________________________________ int [] ar = { 1, 5,3, 9, 2, 0, 5, 4, 9}; 3<5, add 3’s index at the endDeque: 1 2 Output: 5 (First index in deque)At this point our first window with k elements is prepared. Now we will start discarding the elements from the deque which falls outside the window. __________________________________ int [] ar = { 1, 5, 3,9, 2, 0, 5, 4, 9}; 1:Indexes for new window 1-3 so remove indexes less than 1 from deque if present. 2:9>5 and 9>3 Remove 1 2 and add 9’s index.

Deque: 3 Output: 5 9__________________________________ int [] ar = { 1, 5, 3, 9,2, 0, 5, 4, 9} 1:Indexes for new window 2-4 so remove indexes less than 2 from deque if present. 2:2<9, Add 2’s index at the end

Deque: 3 4 Output: 5 9 9__________________________________ int [] ar = { 1, 5, 3, 9, 2,0, 5, 4, 9} 1:Indexes for new window 3-5 so remove indexes less than 3 from deque if present. 2:0< 9, Add 0’s index at the end

Deque:3 4 5 Output: 5 9 9 9__________________________________ int [] ar = { 1, 5, 3, 9, 2, 0,5, 4, 9} 1:Indexes for new window 4-6 so remove indexes less than 4 from deque if present. 2:5>2 and 5>0, Add 5’s index at the end

Deque: 6 Output: 5 9 9 9 5__________________________________ int [] ar = { 1, 5, 3, 9, 2, 0, 5,4, 9} 1:Indexes for new window 5-7 so remove indexes less than 5 from deque if present. So 4 will be removed from deque. 2:4<5, Add 4’s index at the end

Deque: 6 7 Output: 5 9 9 9 5 5__________________________________ int [] ar = { 1, 5, 3, 9, 2, 0, 5, 4,9} 1:Indexes for new window 6-8 so remove indexes less than 6 from deque if present. So 4 will be removed from deque. 2:9>4 and 9>5, So 6 7 will be removed from deque and 9’s index is added.

**Deque: 8 Output: 5 9 9 9 5 5 9 **

**Code:- **

#include <iostream> #include<deque> using namespace std; void maximumSubArrayElement(int *arr,int n,int k){ deque<int> q(k); int i; ///Find the maximum element in first k window for(i=0;i<k;i++){ while((!q.empty()) && arr[i]>arr[q.back()]){ ///if we find the greatest element in the arr the pop the last element(i.e the greatest element of the queue) q.pop_back(); } ///push the element which is greatest in the window or all the element which is come after the greatest element because it can be greatest one in the next window q.push_back(i); } ///Process for the next window for(;i<n;i++){ cout<<arr[q.front()]<<" "; ///1. Remove all the indexes in the deque which is not in the window as those are already printed (Contraction) while((!q.empty()) && (q.front()<=i-k)){ q.pop_front(); } ///2. Remove all the indexes in the deque which is in the window or less than the arr[i] because in every they always less than the arr[i] never in use (Expansion) while((!q.empty()) && arr[i]>arr[q.back()]){ q.pop_back(); } q.push_back(i); } cout<<arr[q.front()]<<endl; } int main() { int n; cin>>n; int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } int k; cin>>k; maximumSubArrayElement(arr,n,k); return 0; }

CommentsNo comment yet.