Sliding Window Algorithm (Track the maximum of each subarray of size k)

by

Objective: Given an array and integer k, write an algorithm to find the maximum element in each subarray of size k.

Example:

int [] nums = { 1, 2, 3, 2, 4, 1, 5, 6,1};
Output: 3, 3, 4, 4, 5, 6, 6
Subarrays –
[1, 2, 3], max = 3
[2, 3, 2], max = 3
[3, 2, 4], max = 4
[2, 4, 1], max = 4
[4, 1, 5], max = 5
[1, 5, 6], max = 6
[5, 6, 1], max = 6

Approach:

Naïve Approach:

  • Have 2 nested loops.
  • Outer loop will navigate the array.
  • Inner loop with track the maximum element in every k elements (all k windows or all subarrays with size k)

Time Complexity: O(nk) where n is the size of array and k is the subarrays size.

Code:


Output:

3 3 4 4 5 6 6

Using Deque: Time complexity O(n)

  1. Use Deque – Double ended queue and store only the data which is necessary or useful. Will store the index of array element in deque to keep track of k elements.
  2. Deque will always have the data for max k elements (window). Initially will create the deque with first k elements and then slide the window by one element at a time, means discard the data which falls outside the new window and all data which falls within the new window.
  3. To create the window for first k elements –
    1. Every new element going into window(deque), Remove all the smaller elements indexes from the deque (since these elements are no longer required) and add the new element at the end.
  1. Once the window is created for first k elements then for every new element going into window(deque) –
    1. Remove the element index which falls outside the window.
    2. And again remove all the smaller elements indexes from the deque (since these elements are no longer required) and add the new element index at the end.
  2. Output from each window will be the first element in the deque (since deque is constructed in descending order as per the steps above.

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

Example:

int [] nums = { 11,12, 13, 12, 14, 11, 10, 9};
K = 3
Create deque for first k elements
int [] nums = { 11,12, 13, 12, 14, 11, 10, 9};
Deque:		Output: 
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
NOTE : we are adding the array index, not element
Deque: 0		Output: 
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
12>11, remove 11 from deque and add 12’s index at the end
Deque: 1		Output: 
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
13>12, remove 12 from deque and add 13’s index at the end
Deque: 2		Output: 13  (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 [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 1-3 so remove indexes less than 1 from deque if present.
2. 12<13, add 12’s index at the end 
Deque: 2 3              Output: 13 13
 __________________________________ 
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 
1. Indexes for new window 2-4 so remove indexes less than 2 from deque if present. 
2. 14>12, remove 12 and 14>13, remove 13. Add 14 at the end
Deque: 4 		Output: 13 13 14
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 3-5 so remove indexes less than 3 from deque if present.
2. 11< 14, Add 11 at the end
Deque: 4 5 		Output: 13 13 14 14
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 4-6 so remove indexes less than 4 from deque if present.
2. 10< 11, Add 10 at the end
Deque: 4 5 6		Output: 13 13 14 14 14
__________________________________
int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9};
1. Indexes for new window 4-7 so remove indexes less than 4 from deque if present. So 4 will be removed from deque.
2. Deque: 5 6
3. 9< 10, Add 9 at the end
Deque: 5 6 7		Output: 13 13 14 14 14 11
__________________________________

Complete Code:


Output:

3 3 4 4 5 6 6

Related Posts: