Used for solving problems that require finding the maximum or minimum of a subarray.
Sliding window problems are problems that need to find subarray or substring.
For a string or an array, sliding-window problems are substring or subarray problems. If you see a substring or a subarray, sliding-window should come to your mind.
For cases, where we are looking for a property EXACTLY K times, use atmost(k)-atmost(k-1), where atmost(k) represents the result if something can vary from 0 till k.
Sliding window problems can be fixed window length or variable window length.
Use two loops. Outer for-loop for j and an inner while loop for i and so the window is (i, j). To avoid end of window corner-case (when the answer lies at the end of the array, e.g.), always update the best, each time. If the answer is not best, it would not do anything.
In terms of coding for the sliding window, we can think of three cases when processing each element: add, delete, and process (the ordering might differ). It is better to keep them separate since adding is something that we always have to do but deleting is something we can do only if the current length is > K. But processing can be done when the current length becomes K. So, the conditions for these three are slightly different.
It is better to think in terms of these three steps
for (int i = 0; i < n; i++) {
// Step1 (DELETE): (i >= K) If greater than K, delete the first one.
// Step2 (ADD): Always add.
// Step3 (Logic to do stuff): (i >= (K-1)) Process the window. Have this condition, if the window length must be K.
}
The problem asks the following. Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. For each window, we need to print the maximum.
For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3, we want the output as follows.
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 Therefore, return the max sliding window as [3,3,5,5,6,7].
This is a sliding window problem of fixed window size the size of window is set to K. We will look at two approaches.
In approach 1, we use a dequeue (of pairs) as part of the solution. This makes the whole thing much simpler.
Following is a code in C++ and it runs in O(N):
void SlidingWindow(int A[], int n, int K) {
deque<int[]> dq; // we maintain ‘window’ to be sorted in descending order
for (int i = 0; i < n; i++) {
// Delete logic. If something is less than A[i], then we
// do not need it since A[i] would be better.
while (!dq.empty() && (dq.peekLast().first <= A[i]))
dq.removeLast(); // this is to keep ‘window’ always sorted
// Add this.
dq.addLast(new int[]{A[i], i});
// Delete logic (drop the element that is outside the window).
while (dq.getFirst()[1] <= i - K)
dq.removeFirst();
// Logic to do stuff
if (i + 1 >= K) // from the first window of length K onwards
printf("%d\n", dq.getFirst()[0]); // the answer for this window
}
}
In approach 2, we use a max Priority Queue.
As opposed to using dequeue (in approach1), this will cost O(NlogN) but is pretty intuitive (logN since the PQ is sorted by max and not by index and so some stale entries might remain in the PQ).
Here is the implementation in Java.
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0]-a[0])); // stores [val, idx]
for (int i = 0; i < n; i++) {
while (!pq.isEmpty() && (pq.peek()[1] < (i-k))) pq.poll();
pq.offer(new int[]{arr[i], i});
currentMax = pq.peek()[0];
// print the currentMax
}