Sliding Window Algorithms

The sliding window algorithm is used to perform the required operation on a specific window size of a given large buffer or array. The window 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 known as the Sliding Window problem or algorithm.

For example, to find the maximum or minimum element from every n element in a given array, a sliding window algorithm is used.

Example:

Input Array: [1 3 -1 -3 5 3 6 7]

Window Size: 3

A maximum element from every 3 elements of the input array:

A minimum element from every 3 elements of the input array:

Methods to find the sum of 3 elements:

Method 1:

The first way is to use quicksort, when the pivot is at the Kth position, all elements on the right side are greater than the pivot, hence, all elements on the left side automatically become K smallest elements of the given array.

Method 2:

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

Method 3:

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

Space Complexity: 0(n)

Time Complexity: 0(n)

Not so bad, huh? Wishing everyone good luck with algo practice!