Sliding Window Maximum (Maximum of all subarrays of size k) Part II

Hello Everyone,

In continuation with last post.

Method 3: This method uses Deque to solve the above problem.

Approach:
Create a Deque, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on right side of it in current window. Process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear/back of Qi is the smallest of current window.

Algorithm:

  1. Create a deque to store k elements.
  2. Run a loop and insert first k elements in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element , if it is so remove the element from the back of the deque, until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
  3. Now, run a loop from k to end of the array.
  4. Print the front element of the deque.
  5. Remove the element from the front of the queue if they are out of the current window.
  6. Insert the next element in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element , if it is so remove the element from the back of the deque, until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
  7. Print the maximum element of the last window.

Implementation:

// CPP program for the above approach

#include <bits/stdc++.h>

using namespace std;

// A Dequeue (Double ended queue) based

// method for printing maximum element of

// all subarrays of size k

void printKMax( int arr[], int n, int k)

{

// Create a Double Ended Queue,

// Qi that will store indexes

// of array elements

// The queue will store indexes

// of useful elements in every

// window and it will

// maintain decreasing order of

// values from front to rear in Qi, i.e.,

// arr[Qi.front[]] to arr[Qi.rear()]

// are sorted in decreasing order

std::deque< int > Qi(k);

/* Process first k (or first window)

elements of array */

int i;

for (i = 0; i < k; ++i)

{

// For every element, the previous

// smaller elements are useless so

// remove them from Qi

while ((!Qi.empty()) && arr[i] >=

arr[Qi.back()])

// Remove from rear

Qi.pop_back();

// Add new element at rear of queue

Qi.push_back(i);

}

// Process rest of the elements,

// i.e., from arr[k] to arr[n-1]

for (; i < n; ++i)

{

// The element at the front of

// the queue is the largest element of

// previous window, so print it

cout << arr[Qi.front()] << " " ;

// Remove the elements which

// are out of this window

while ((!Qi.empty()) && Qi.front() <=

i - k)

// Remove from front of queue

Qi.pop_front();

// Remove all elements

// smaller than the currently

// being added element (remove

// useless elements)

while ((!Qi.empty()) && arr[i] >=

arr[Qi.back()])

Qi.pop_back();

// Add current element at the rear of Qi

Qi.push_back(i);

}

// Print the maximum element

// of last window

cout << arr[Qi.front()];

}

// Driver code

int main()

{

int arr[] = { 12, 1, 78, 90, 57, 89, 56 };

int n = sizeof (arr) / sizeof (arr[0]);

int k = 3;

printKMax(arr, n, k);

return 0;

}

Output

78 90 90 90 89

Complexity Analysis:

  • Time Complexity: O(n).
    It seems more than O(n) at first look. It can be observed that every element of array is added and removed at most once. So there are total 2n operations.
  • Auxiliary Space: O(k).
    Elements stored in the dequeue take O(k) space.

Method 4: This method uses Max-Heap to solve the above problem.

Approach:
In the above-mentioned methods, one of them was using AVL tree. This approach is very similar to that approach. The difference is that instead of using the AVL tree, Max-Heap will be used in this approach. The elements of the current window will be stored in the Max-Heap and the maximum element or the root will be printed in each iteration.
Max-heap is a suitable data structure as it provides constant-time retrieval and logarithmic time removal of both the minimum and maximum elements in it, i.e. it takes constant time to find the maximum element and insertion and deletion takes log n time.

Algorithm:

  1. Pick first k elements and create a max heap of size k.
  2. Perform heapify and print the root element.
  3. Store the next and last element from the array
  4. Run a loop from k – 1 to n
  • Replace the value of element which is got out of the window with new element which came inside the window.
  • Perform heapify.
  • Print the root of the Heap.