Window Sliding Technique - GeeksforGeeks
Window Sliding Technique 2
This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.
http://www.geeksforgeeks.org/sum-minimum-maximum-elements-subarrays-size-k/
http://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/
http://www.geeksforgeeks.org/count-distinct-elements-in-every-window-of-size-k/
http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/
How to handle negative numbers?
The above solution may not work if input array contains negative numbers. For example arr[] = {- 8, 1, 4, 2, -6}. To handle negative numbers, add a condition to ignore subarrays with negative sums.
http://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/
Read full article from Window Sliding Technique - GeeksforGeeks
Window Sliding Technique 2
This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.
Given an array of integers of size ‘n’. Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.
So, let’s analyze the problem with Brute Force Approach. We start with first index and sum till k-th element. We do it for all possible consecutive blocks or groups of k elements. This method requires nested for loop, the outer for loop starts with the starting element of the block of k elements and the inner or the nested loop will add up till the k-th element.
int maxSum(int arr[], int n, int k){ // Initialize result int max_sum = INT_MIN ; // Consider all blocks starting with i. for (int i=0; i<n-k+1; i++) { int current_sum = 0; for (int j=0; j<k; j++) current_sum = current_sum + arr[i+j]; // Update result if required. max_sum = max(current_sum , max_sum ); } return max_sum;}
The technique can be best understood with the window pane in bus, consider a window of length n and the pane which is fixed in it of length k. Consider, initially the pane is at extreme left i.e., at 0 units from the left. Now, co-relate the window with array arr[] of size n and plane with current_sum of size k elements. Now, if we apply force on the window such that it moves a unit distance ahead. The pane will cover next k consecutive elements.
We can use this technique to find max/min k-subarray, XOR, product, sum, etc.
int maxSum(int arr[], int n, int k){ // k must be greater if (n < k) { cout << "Invalid"; return -1; } // Compute sum of first window of size k int max_sum = 0; for (int i=0; i<k; i++) max_sum += arr[i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. int window_sum = max_sum; for (int i=k; i<n; i++) { window_sum += arr[i] - arr[i-k]; max_sum = max(max_sum, window_sum); } return max_sum;}http://www.geeksforgeeks.org/sum-minimum-maximum-elements-subarrays-size-k/
Given an array of both positive and negative integers, the task is to compute sum of minimum and maximum elements of all sub-array of size k.
Method 2 (Efficient using Dequeue)
The idea is to use Dequeue data structure and sliding window concept. We create two empty double ended queues of size k (‘S’ , ‘G’) that only store indexes of elements of current window that are not useless. An element is useless if it can not be maximum or minimum of next subarrays.
The idea is to use Dequeue data structure and sliding window concept. We create two empty double ended queues of size k (‘S’ , ‘G’) that only store indexes of elements of current window that are not useless. An element is useless if it can not be maximum or minimum of next subarrays.
a) In deque 'G', we maintain decreasing order of
values from front to rear
b) In deque 'S', we maintain increasing order of
values from front to rear
1) First window size K
1.1) For deque 'G', if current element is greater
than rear end element, we remove rear while
current is greater.
1.2) For deque 'S', if current element is smaller
than rear end element, we just pop it while
current is smaller.
1.3) insert current element in both deque 'G' 'S'
2) After step 1, front of 'G' contains maximum element
of first window and front of 'S' contains minimum
element of first window. Remaining elements of G
and S may store maximum/minimum for subsequent
windows.
3) After that we do traversal for rest array elements.
3.1) Front element of deque 'G' is greatest and 'S'
is smallest element of previous window
3.2) Remove all elements which are out of this
window [remove element at front of queue ]
3.3) Repeat steps 1.1 , 1.2 ,1.3
4) Return sum of minimum and maximum element of all
sub-array size k.
int SumOfKsubArray(int arr[] , int n , int k){ int sum = 0; // Initialize result // The queue will store indexes of useful elements // in every window // In deque 'G' we maintain decreasing order of // values from front to rear // In deque 'S' we maintain increasing order of // values from front to rear deque< int > S(k), G(k); // Process first window of size K int i = 0; for (i = 0; i < k; i++) { // Remove all previous greater elements // that are useless. while ( (!S.empty()) && arr[S.back()] >= arr[i]) S.pop_back(); // Remove from rear // Remove all previous smaller that are elements // are useless. while ( (!G.empty()) && arr[G.back()] <= arr[i]) G.pop_back(); // Remove from rear // Add current element at rear of both deque G.push_back(i); S.push_back(i); } // Process rest of the Array elements for ( ; i < n; i++ ) { // Element at the front of the deque 'G' & 'S' // is the largest and smallest // element of previous window respectively sum += arr[S.front()] + arr[G.front()]; // Remove all elements which are out of this // window while ( !S.empty() && S.front() <= i - k) S.pop_front(); while ( !G.empty() && G.front() <= i - k) G.pop_front(); // remove all previous greater element that are // useless while ( (!S.empty()) && arr[S.back()] >= arr[i]) S.pop_back(); // Remove from rear // remove all previous smaller that are elements // are useless while ( (!G.empty()) && arr[G.back()] <= arr[i]) G.pop_back(); // Remove from rear // Add current element at rear of both deque G.push_back(i); S.push_back(i); } // Sum of minimum and maximum element of last window sum += arr[S.front()] + arr[G.front()]; return sum;}http://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/
Given an integer array of size n, find the maximum of the minimum’s of every window size in the array. Note that window size varies from 1 to n.
A Simple Solution is to go through all windows of every size, find maximum of all windows
Time complexity of above solution can be upper bounded by O(n3).
void printMaxOfMin(int arr[], int n){ // Consider all windows of different sizes starting // from size 1 for (int k=1; k<=n; k++) { // Initialize max of min for current window size k int maxOfMin = arr[0]; // Traverse through all windows of current size k for (int i = 0; i <= n-k; i++) { // Find minimum of current window int min = arr[i]; for (int j = 1; j < k; j++) { if (arr[i+j] < min) min = arr[i+j]; } // Update maxOfMin if required if (min > maxOfMin) maxOfMin = min; } // Print max of min for current window size cout << maxOfMin << " "; }}
We can solve this problem in O(n) time using an Efficient Solution. The idea is to extra space. Below are detailed steps.
Step 1: Find indexes of next smaller and previous smaller for every element. Next smaller is the largest element on right side of arr[i] such that the element is smaller than arr[i]. Similarly, previous smaller element is on left side/
If there is no smaller element on right side, then next smaller is n. If there is no smaller on left side, then previous smaller is -1.
Step 1: Find indexes of next smaller and previous smaller for every element. Next smaller is the largest element on right side of arr[i] such that the element is smaller than arr[i]. Similarly, previous smaller element is on left side/
If there is no smaller element on right side, then next smaller is n. If there is no smaller on left side, then previous smaller is -1.
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of next smaller is {7, 4, 4, 4, 7, 6, 7}.
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of previous smaller is {-1, 0, 1, 2, -1, 4, 4}
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of previous smaller is {-1, 0, 1, 2, -1, 4, 4}
This step can be done in O(n) time using the approach discussed in next greater element.
Step 2: Once we have indexes of next and previous smaller, we know that arr[i] is a minimum of a window of length “right[i] – left[i] – 1”. Lengths of windows for which the elements are minimum are {7, 3, 2, 1, 7, 1, 2}. This array indicates, first element is minimum in window of size 7, second element is minimum in window of size 1, and so on.
Create an auxiliary array ans[n+1] to store the result. Values in ans[] can be filled by iterating through right[] and left[]
for (int i=0; i < n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;
// a[i] is the possible answer for
// this length len interval
ans[len] = max(ans[len], arr[i]);
}
We get the ans[] array as {0, 70, 30, 20, 0, 0, 0, 10}. Note that ans[0] or answer for length 0 is useless.
Step 3:Some entries in ans[] are 0 and yet to be filled. For example, we know maximum of minimum for lengths 1, 2, 3 and 7 are 70, 30, 20 and 10 respectively, but we don't know the same for lengths 4, 5 and 6.
Below are few important observations to fill remaining entries
a) Result for length i, i.e. ans[i] would always be greater or same as result for length i+1, i.e., an[i+1].
b) If ans[i] is not filled it means there is no direct element which is minimum of length i and therefore either the element of length ans[i+1], or ans[i+2], and so on is same as ans[i]
So we fill rest of the entries using below loop.
Below are few important observations to fill remaining entries
a) Result for length i, i.e. ans[i] would always be greater or same as result for length i+1, i.e., an[i+1].
b) If ans[i] is not filled it means there is no direct element which is minimum of length i and therefore either the element of length ans[i+1], or ans[i+2], and so on is same as ans[i]
So we fill rest of the entries using below loop.
for (int i=n-1; i>=1; i--)
ans[i] = max(ans[i], ans[i+1]);
void printMaxOfMin(int arr[], int n){ stack<int> s; // Used to find previous and next smaller // Arrays to store previous and next smaller int left[n+1]; int right[n+1]; // Initialize elements of left[] and right[] for (int i=0; i<n; i++) { left[i] = -1; right[i] = n; } // Fill elements of left[] using logic discussed on for (int i=0; i<n; i++) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); if (!s.empty()) left[i] = s.top(); s.push(i); } // Empty the stack as stack is going to be used for right[] while (!s.empty()) s.pop(); // Fill elements of right[] using same logic for (int i = n-1 ; i>=0 ; i-- ) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); if(!s.empty()) right[i] = s.top(); s.push(i); } // Create and initialize answer array int ans[n+1]; for (int i=0; i<=n; i++) ans[i] = 0; // Fill answer array by comparing minimums of all // lengths computed using left[] and right[] for (int i=0; i<n; i++) { // length of the interval int len = right[i] - left[i] - 1; // arr[i] is a possible answer for this length // 'len' interval, check if arr[i] is more than // max for 'len' ans[len] = max(ans[len], arr[i]); } // Some entries in ans[] may not be filled yet. Fill // them by taking values from right side of ans[] for (int i=n-1; i>=1; i--) ans[i] = max(ans[i], ans[i+1]); // Print the result for (int i=1; i<=n; i++) cout << ans[i] << " ";}http://www.geeksforgeeks.org/count-distinct-elements-in-every-window-of-size-k/
Given an array of size n and an integer k, return the of count of distinct numbers in all windows of size k.
A Simple Solution is to traverse the given array, consider every window in it and count distinct elements in the window.
int countWindowDistinct(int win[], int k){ int dist_count = 0; // Traverse the for (int i=0; i<k; i++) { // Check if element arr[i] exists in arr[0..i-1] int j; for (j=0; j<i; j++) if (win[i] == win[j]) break; if (j==i) dist_count++; } return dist_count;}// Counts distinct elements in all windows of size kvoid countDistinct(int arr[], int n, int k){ // Traverse through every window for (int i=0; i<=n-k; i++) cout << countWindowDistinct(arr+i, k) << endl;}
Time complexity of the above solution is O(nk2). We can improve time complexity to O(nkLok) by modifying countWindowDistinct() to use sorting. The function can further be optimized to use hashing to find distinct elements in a window. With hashing the time complexity becomes O(nk). Below is a different approach that works in O(n) time.
An Efficient Solution is to use the count of previous window, while sliding the window. The idea is to create a hash map that stores elements of current widow. When we slide the window, we remove an element from hash and add an element. We also keep track of distinct elements. Below is algorithm.
1) Create an empty hash map. Let hash map be hM
2) Initialize distinct element count ‘dist_count’ as 0.
3) Traverse through first window and insert elements of first window to hM. The elements are used as key and their counts as value in hM. Also keep updating ‘dist_count’
4) Print ‘dist_count’ for first window.
3) Traverse through remaining array (or other windows).
….a) Remove the first element of previous window.
…….If the removed element appeared only once
…………..remove it from hM and do “dist_count–”
…….Else (appeared multiple times in hM)
…………..decrement its count in hM
….a) Remove the first element of previous window.
…….If the removed element appeared only once
…………..remove it from hM and do “dist_count–”
…….Else (appeared multiple times in hM)
…………..decrement its count in hM
….a) Add the current element (last element of new window)
…….If the added element is not present in hM
…………..add it to hM and do “dist_count++”
…….Else (the added element appeared multiple times)
…………..increment its count in hM
…….If the added element is not present in hM
…………..add it to hM and do “dist_count++”
…….Else (the added element appeared multiple times)
…………..increment its count in hM
static void countDistinct(int arr[], int k) { // Creates an empty hashMap hM HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); // initialize distinct element count for // current window int dist_count = 0; // Traverse the first window and store count // of every element in hash map for (int i = 0; i < k; i++) { if (hM.get(arr[i]) == null) { hM.put(arr[i], 1); dist_count++; } else { int count = hM.get(arr[i]); hM.put(arr[i], count+1); } } // Print count of first window System.out.println(dist_count); // Traverse through the remaining array for (int i = k; i < arr.length; i++) { // Remove first element of previous window // If there was only one occurrence, then // reduce distinct count. if (hM.get(arr[i-k]) == 1) { hM.remove(arr[i-k]); dist_count--; } else // reduce count of the removed element { int count = hM.get(arr[i-k]); hM.put(arr[i-k], count-1); } // Add new element of current window // If this element appears first time, // increment distinct element count if (hM.get(arr[i]) == null) { hM.put(arr[i], 1); dist_count++; } else // Increment distinct element count { int count = hM.get(arr[i]); hM.put(arr[i], count+1); } // Print count of current window System.out.println(dist_count); } }http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/
Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.
int smallestSubWithSum(int arr[], int n, int x){ // Initialize current sum and minimum length int curr_sum = 0, min_len = n+1; // Initialize starting and ending indexes int start = 0, end = 0; while (end < n) { // Keep adding array elements while current sum // is smaller than x while (curr_sum <= x && end < n) curr_sum += arr[end++]; // If current sum becomes greater than x. while (curr_sum > x && start < n) { // Update minimum length if needed if (end - start < min_len) min_len = end - start; // remove starting elements curr_sum -= arr[start++]; } } return min_len;}int smallestSubWithSum(int arr[], int n, int x){ // Initilize length of smallest subarray as n+1 int min_len = n + 1; // Pick every element as starting point for (int start=0; start<n; start++) { // Initialize sum starting with current start int curr_sum = arr[start]; // If first element itself is greater if (curr_sum > x) return 1; // Try different ending points for curremt start for (int end=start+1; end<n; end++) { // add last element to current sum curr_sum += arr[end]; // If sum becomes more than x and length of // this subarray is smaller than current smallest // length, update the smallest length (or result) if (curr_sum > x && (end - start + 1) < min_len) min_len = (end - start + 1); } } return min_len;}How to handle negative numbers?
The above solution may not work if input array contains negative numbers. For example arr[] = {- 8, 1, 4, 2, -6}. To handle negative numbers, add a condition to ignore subarrays with negative sums.
int smallestSubWithSum(int arr[], int n, int x){ // Initialize current sum and minimum length int curr_sum = 0, min_len = n+1; // Initialize starting and ending indexes int start = 0, end = 0; while (end < n) { // Keep adding array elements while current sum // is smaller than x while (curr_sum <= x && end < n) { // Ignore subarrays with negative sum if // x is positive. if (curr_sum <= 0 && x > 0) { start = end; curr_sum = 0; } curr_sum += arr[end++]; } // If current sum becomes greater than x. while (curr_sum > x && start < n) { // Update minimum length if needed if (end - start < min_len) min_len = end - start; // remove starting elements curr_sum -= arr[start++]; } } return min_len;}
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Method 3 (A O(n) method: use Dequeue)
We create a Dequeue, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
We create a Dequeue, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
Time Complexity: O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of array is added and removed at most once. So there are total 2n operations.
Auxiliary Space: O(k)
Auxiliary Space: O(k)
// A Dequeue (Double ended queue) based method for printing maixmum element of// all subarrays of size kvoid printKMax(int arr[], int n, int k){ // Create a Double Ended Queue, Qi that will store indexes of array elements // The queue will store indexes of useful elements in every window and it will // maintain decreasing order of values from front to rear in Qi, i.e., // arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order std::deque<int> Qi(k); /* Process first k (or first window) elements of array */ int i; for (i = 0; i < k; ++i) { // For very element, the previous smaller elements are useless so // remove them from Qi while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); // Remove from rear // Add new element at rear of queue Qi.push_back(i); } // Process rest of the elements, i.e., from arr[k] to arr[n-1] for ( ; i < n; ++i) { // The element at the front of the queue is the largest element of // previous window, so print it cout << arr[Qi.front()] << " "; // Remove the elements which are out of this window while ( (!Qi.empty()) && Qi.front() <= i - k) Qi.pop_front(); // Remove from front of queue // Remove all elements smaller than the currently // being added element (remove useless elements) while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); // Add current element at the rear of Qi Qi.push_back(i); } // Print the maximum element of last window cout << arr[Qi.front()];}
Method 2 (Use Self-Balancing BST)
1) Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size k.
2) Run a loop for i = 0 to n – k
…..a) Get the maximum element from the BST, and print it.
…..b) Search for arr[i] in the BST and delete it from the BST.
…..c) Insert arr[i+k] into the BST.
1) Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size k.
2) Run a loop for i = 0 to n – k
…..a) Get the maximum element from the BST, and print it.
…..b) Search for arr[i] in the BST and delete it from the BST.
…..c) Insert arr[i+k] into the BST.
Time Complexity: Time Complexity of step 1 is O(kLogk). Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(kLogk + (n-k+1)*Logk) which can also be written as O(nLogk).
void printKMax(int arr[], int n, int k){ int j, max; for (int i = 0; i <= n-k; i++) { max = arr[i]; for (j = 1; j < k; j++) { if (arr[i+j] > max) max = arr[i+j]; } printf("%d ", max); }}
