|
This post is completed by 1 user
|
Add to List |
261. Sliding Window Algorithm (Track the maximum of each subarray of size k)
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.
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, which means discarding 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 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
__________________________________
Output:
3 3 4 4 5 6 6