Heaps : Sliding Window Algorithm

Sliding Window Algorithm

Given a larger integer buffer/array (say size, x), window size (say, n) and a number (say, k). Windows starts from the 1st element and keeps shifting right by one element. The objective is to find the minimum k numbers present in each window. This is commonly know as sliding window problem or algorithm.
This problem regularly features in programming interview questions. Basic concept is very simple, but some more variables thrown into question, that makes it more interesting.

Analysis
Given an array of integers, how do we find K smallest or largest elements?  There are a few ways to do so.

Method 1 :
First way is to use quick sort, when pivot is at Kth position, all elements on the right side are greater than pivot, hence, all elements on the left side automatically become K smallest elements of given array.

Method 2 :
Keep an array of K elements, Fill it with first K elements of given input array. 
Now from K+1 element, check if the current element is less than the maximum element in the auxiliary array, if yes, add this element into array. 
Only problem with above solution is that we need to keep track of maximum element. Still workable.
How can we keep track of maximum element in set of integer? Think heap. Think Max heap.

Method 3: 
Great! In O(1) we would get the max element among K elements already chose as smallest K elements . If max in current set is greater than newly considered element, we need to remove max and introduce new element in set of K smallest element. Heapify again to maintain the heap property.
Now we can easily get K minimum elements in array of N.

Sliding window algorithm uses one of above mentioned methods to find Kth smallest element.

Rest of the problem is just to adjust our array consideration w.r.t to start and end index in bigger array.

Following figures explain how window slides and how heap is updated.
1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap.



2. Now window moves one step ahead, so heap is updated again.



3. Again windows slides forward but this time, max heap is not updated.

Code

Output of above code for input in figure would be with window as 5 and K =4


Complexity Analysis

Worst case complexity of sliding window algorithm would be O(N^2 * K). K is included as it takes O(K) complexity to build heap of K elements.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s