**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**:

**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:**

**Output:**

3 3 4 4 5 6 6