## CodingBison

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.

### Coding Approach

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 lenght 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.
// Step3 (Logic to do stuff): (i >= (K-1)) Process the window. Have this condition, if the window length must be K.
}
```

#### Example: Sliding Window Maximum

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 deque (of pairs) as part of the solution. This makes the whole thing much simpler.

• The deque is a pair of (element value and its index).
• For each element added in the deque, we make a pair of its value and its index.
• When we have i, we delete all values that are prior to i-K.
• Also, when we add a[i], we delete all values that are smaller than it.

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

// 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.

• We use a max PQ that stores both the value of and its index (once again a pair).
• When we process i, we pop() all the values in Priority Queue that are less than (i-k). Since PQ will always give us the maximum element left, this makes things simpler.

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
}
```