Maximum numbers in a sliding window

Given an array of N values and a value K, Write a program to print the maximum of all the sliding windows (sub-array) of size K.

For example let us consider the following array as input

[4, 5, 3, 2, 6, 1, 2, 3, 8, 4]

Let as take the sliding window of size 3. The output will be as follows

Sliding Window Maximum

———————————

[4, 5, 3] 5

[5, 3, 2] 5

[3, 2, 6] 6

[2, 6, 1] 6

[6, 1, 2] 6

[1, 2, 3] 3

[2, 3, 8] 8

[3, 8, 4] 8

The brute force solution can be to find the maximum of each sliding window when we move forward by one element. In an array of size n, there will be (n-k+1) sliding windows of size k. For each window, it takes O(k) time to find the maximum. So, it’s time complexity is O( (n-k+1)* k ) ~= O(n*k).

Can we do better than this?

Yes! this problem can be efficiently solved using the dequeue data structure. Dequeue data structure supports inserting and deleting the elements at both ends of the queue via push_back(), pop_back(), push_front() and pop_front(). Here is how the algorithm works.

We maintain the indices of elements of the current window in a dequeue. We also make sure that the maximum element always appear in the front of the queue. The new element is added at the back of the queue by deleting all the smaller elements before it. We will also delete the element just went out of scope (previous window element). In each iteration we print the front of the queue which is maximum.

Here is the C++ implementation of this algorithm.

	#include <iostream>
	#include <vector>
	#include <deque>

	using namespace std;

	void printMaxSlidingWindow( vector<int> & array, int k )
	{
	deque<int> indQueue;
	int i;

	//Initial sliding window
	for( i = 0; i < k ; i++ )
	{
	//Delete all smaller elements before pushing the current element
	while( !indQueue.empty() && array[indQueue.back()] <= array[i] )
	indQueue.pop_back();

	indQueue.push_back(i);
	}

	for( ; i < array.size(); i++ )
	{
	cout << array[indQueue.front()] << " ";

	while( !indQueue.empty() && array[indQueue.back()] <= array[i] )
	indQueue.pop_back();

	//If previous window element is present, remove it
	if( !indQueue.empty() && indQueue.front() <= i-k )
	indQueue.pop_front();

	indQueue.push_back(i);
	}

	//print the maximum of last sliding window
	cout << array[indQueue.front()] << endl;
	}

	//Brute force method
	void printMax( vector<int> & array, int k )
	{
	int i, j;

	int max = INT_MIN;

	for( i = 0; i < k; i++ )
	{
	if( max < array[i] )
	max = array[i];
	}

	cout << max << " ";

	for( i = 0; i < array.size()-k; i++ )
	{
	max = array[i];

	for( j = i+1; j < i+k; j++ )
	{
	if( max < array[j] )
	max = array[j];
	}
	cout << max << " ";
	}
	}

	int main()
	{
	int n,k;
	cin >> n >> k;
	vector<int> array;

	int i;
	for( i = 0; i < n; i++ )
	{
	int num;
	cin >> num;
	array.push_back(num);
	}

	printMaxSlidingWindow( array, k );

	return 0;
	}

view raw MaximumSlidingWindow.cpp hosted with

by GitHub

Leave a Reply Cancel reply