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:

public class SlidingWindowMaximumNaive {
public void slidingWindow(int [] nums, int k){
for (int i = 0; i <nums.length – k ; i++) {
int max = nums[i];
for (int j = 1; j<=k ; j++) {
if(nums[i+j]>max)
max = nums[i+j];
}
System.out.print(max + " ");
}
}
public static void main(String[] args) {
int [] nums = {1, 2, 3, 2, 4, 1, 5, 6, 1};
int k = 3;
SlidingWindowMaximumNaive s = new SlidingWindowMaximumNaive();
s.slidingWindow(nums, k);
}
}

view raw
SlidingWindowMaximumNaive.java
hosted with ❤ by GitHub


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:

import java.util.Deque;
import java.util.LinkedList;
public class SlidingWindowMaximum_Deque {
public void slidingWindow(int [] nums, int k){
Deque<Integer> deque = new LinkedList<>();
//Step 1: handle first k elements in sliding window
for (int i = 0; i <k ; i++) {
//remove all the elements which are smaller than the current elements
while(deque.isEmpty()==false && nums[deque.peekLast()]<=nums[i])
deque.removeLast();
//add new element at the end
deque.addLast(i);
}
//Step 2: handle rest of the element, one at a time nums[k] to nums[n-1]
for (int i = k; i <nums.length ; i++) {
//before we do anything, print the first element in deque
//since its a maximum among previous k elements
System.out.print(nums[deque.peekFirst()] + " ");
//Now remove the elements which are out for next window (next k elements)
while(deque.isEmpty()==false && deque.peekFirst()<=i–k)
deque.removeFirst();
//Add the next element in the window = index i
//remove all the elements which are smaller than the next element = index i
while(deque.isEmpty()==false && nums[deque.peekLast()]<=nums[i])
deque.removeLast();
//add new element at the end
deque.addLast(i);
}
//to print the last max element
System.out.print(nums[deque.peekFirst()] + " ");
}
public static void main(String[] args) {
int [] nums = {1, 2, 3, 2, 4, 1, 5, 6, 1};
int k = 3;
SlidingWindowMaximum_Deque s = new SlidingWindowMaximum_Deque();
s.slidingWindow(nums, k);
}
}

view raw
SlidingWindowMaximum_Deque.java
hosted with ❤ by GitHub


Output:

3 3 4 4 5 6 6

Related Posts: