**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, 6Subarrays – [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); | |

} | |

} |

**Output**:

3 3 4 4 5 6 6

**Using Deque: Time complexity O(n)**

- 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.
- 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.
- To create the window for first k elements –
- 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.

- Once the window is created for first k elements then for every new element going into window(deque) –
- Remove the element index which falls outside the window.
- 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.

- 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 elementDeque: 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 endDeque: 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 endDeque: 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 endDeque: 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 endDeque: 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 endDeque: 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 endDeque: 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 endDeque: 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); | |

} | |

} |

**Output:**

3 3 4 4 5 6 6