# Sliding Windows Problem Introduction

Pattern: Linked list or arrays find something among all contigious sub array of some given size.

Problems Discussed

## Inverted Sliding Window [Microsoft OA]

### Problem Statement

Suppose $$A[n]$$ is an array of integers. Identify a $$r$$ length window such that $$A[i] \mid \forall \: i \in [n] \text{ except for } \left[k, k+r \right)$$ for some $$k \in [n - r]$$ has most number of unique elements.

### Approach

• In first step we calculate the unique elements outside the first window (from $$0 \to r - 1$$),
• Next we slide the window to $$(1 \to r)$$. In this case the unique element map will add the $$0^{\text{th}}$$ element and remove the $$r^{\text{th}}$$ element (think of it as the inverted sliding window). We are sliding a window but we are interested outside the window.
• Following is an illustration as to how this window works. Notice the elements outside the bucket rather than the inside. Which is incoming and which is outgoing.

### Code

#include <climits>
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
int testcase;
cin >> testcase;

while (testcase--) {
int n, r;
cin >> n >> r;

if (n == r) {
cout << "0" << endl;
break;
}

int a[n];

for (int i = 0; i < n; i++) {
cin >> a[i];
}

unordered_map<int, int> freq;

int maximumUniqueWindow = INT_MIN;

// outside first window
int index = 0;
while (index < n) {
if (not(index < r and index >= 0)) {
freq[a[index]]++;
}

index++;
}

maximumUniqueWindow = std::max(maximumUniqueWindow, (int)freq.size());

// for rest of the outside windows
int window_start = 1;
int window_end = r;

int maxWindowStart = 0;
int maxWindowEnd = r - 1;

while (window_end < n) {
// outgoing + incoming from the outside window
int outgoing = a[window_end];
int incoming = a[window_start - 1];

freq[outgoing]--;

if (not freq[outgoing]) {
freq.erase(outgoing);
}

freq[incoming]++;

int currentsize = freq.size();

if (currentsize >= maximumUniqueWindow) {
maximumUniqueWindow = currentsize;

maxWindowStart = window_start;
maxWindowEnd = window_end;
}

window_start++;
window_end++;
}

cout << maximumUniqueWindow << endl;
}
}


## Other problems

Given an array, find the average of all contiguous subarrays of size ‘K’ in it.

For a given array: $$[1, 3, 2, 6, -1, 4, 1, 8, 2]$$ and $$K=5$$ means find the average of all the contiguous subarrays of size ‘5’ in the given array.

1. For the first 5 numbers (subarray from index 0-4), the average is $$(1+3+2+6−1)/5=2.2$$
2. The average of next 5 numbers (subarray from index 1-5) is: $$(3+2+6-1+4)/5 = 2.8$$
3. For the next 5 numbers (subarray from index 2-6), the average is: 2.5 and so on.

Here is the final output containing the averages of all contiguous subarrays of size 5: Output: [2.2, 2.8, 2.4, 3.6, 2.8]

### Brute force apprach

A brute-force algorithm will be to calculate the sum of every 5-element contiguous subarray of the given array and divide the sum by ‘5’ to find the average.

def brute_force(array: list[int], K:int) -> list[int]:

# Keep track of the avgs
avgs: list[int] = []

# Start from 0 and go to the next 5 elements and find the average
for i in range(0, len(array)- K+1):
sum: int = 0
for j in range(i, i+K):
sum += array[j]

avg: float = sum / K
avgs.append(avg)

return avgs


mainarray: list[int] = [1, 3, 2, 6, -1, 4, 1, 8, 2]
K: int = 5  # find max of this size for given array

a: list[int] = brute_force(mainarray, K)

from rich.console import Console  # For printing purposes

console = Console()
console.print(a)

Output
[2.2, 2.8, 2.4, 3.6, 2.8]


### Problems with this apporach

• Time complexity is huge $$O(N * K)$$.
• We are summing up same elements over and over again. For two consecutive subarrays of size 5 we could just add the new incoming elements and subtract the outgoing elements.

This will reduce the cost to $$O(N)$$ with just one time $$O(K)$$ summing up program.

def optimized(array: list[int], K: int) -> list[int]:

if K > len(array):
raise IndexError("Error Bro")

# Keep track of all the averages
avgs: list[int] = []

# Start from 0 and go to the next K elements and find the average
sumtillK: int = 0
for i in range(0, K):
sumtillK += array[i]

avgs.append(sumtillK / K)

# If the size of the array is the size of the window then just return
if K == len(array):
return avgs

# From K+1 to Last element for each sliding window add the last
# element and subtract the first element

# Leave the first element and then start from 2nd elemenet
# and slide smoothly
for i in range(1, len(array) - K + 1):
sumtillK = sumtillK - array[i - 1] + array[i + K - 1]
avgs.append(sumtillK / K)

return avgs


### Optimized approach with while loop

def optimized_while(array: list[int], K: int) -> list[int]:

avgs: list[int] = []

if K > len(array):
raise IndexError("Error Bro")

sumtillk: int = 0

for i in range(0, K):
sumtillk += array[i]

avgs.append(sumtillk / K)

# Leave the first element and then start from 2nd elemenet
# and slide smoothly
index: int = 1

while index != (len(array) - K + 1):
sumtillk = sumtillk - array[index - 1] + array[index + K - 1]
avgs.append(sumtillk / K)
index += 1

return avgs

b: list[int] = optimized(mainarray, K)
c: list[int] = optimized_while(mainarray, K)
console.print(b)
console.print(c)


Output

[2.2, 2.8, 2.4, 3.6, 2.8]
[2.2, 2.8, 2.4, 3.6, 2.8]


## Maximum Sum subarray of size K

### Problem Statement

Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’.

### Examples

Input: [2, 1, 5, 1, 3, 2], k=3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

---

Input: [2, 3, 4, 1, 5], k=2
Output: 7
Explanation: Subarray with maximum sum is [3, 4].


### Approach [Naive on back of the envelope approach]

def mss(array: list[int], k:int) -> int:
maximum: int = 0
sumtillK: int = 0

for i in range(0, k):
sumtillK += array[i]
maximum = sumtillK

idx: int = 1

while idx != len(array) - k:
sumtillK = sumtillK - array[idx-1] + array[idx + k -1]
maximum = max(maximum, sumtillK)
idx += 1

return maximum

mainarray: list[int] = [2, 1, 5, 1, 3, 2]
K: int = 3  # find max of this size for given array
a2: list[int] = [2, 3, 4, 1, 5]
k2 = 2

a: int = mss(mainarray, K)
print(a) # -> 9

b: int = mss(a2, k2)
print(b) # -> 7


### Time complexity

Only one pass of the array so the time complexity is $$O(N)$$

## Smallest subarray with a given sum

### Problem statement

Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.

### Examples

Input: [2, 1, 5, 2, 3, 2], S=7
Output: 2
Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].

---

Input: [2, 1, 5, 2, 8], S=7
Output: 1
Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].

---
Input: [3, 4, 1, 1, 6], S=8
Output: 3
Explanation: Smallest subarrays with a sum greater than or equal to '8' are [3, 4, 1] or [1, 1, 6].


### Brute force approach

Key takeway approach

💡 For each size of window find out if the sum is greater or equal to the target?

testcase1: list[int] = [2, 1, 5, 2, 3, 2]
testcase1s: int = 7

testcase2: list[int] = [3, 4, 1, 1, 6]
testcase2s: int = 8

testcase3: list[int] = [2, 1, 5, 2, 8]
testcase3s: int = 7

# Brute force approach
def ssgs(array: list[int], s: int) -> int:
def subroutine(array: list[int], ws: int, target: int):
if ws == 1:
for entires in array:
if entires >= target:
return 1

summation: int = 0
for i in range(0, ws):
summation += array[i]
if summation >= target:
return ws

index = 1
while index < len(array) - ws:
summation = summation - array[index - 1] + array[index + ws - 1]
if summation >= target:
return ws
index += 1

return -1

window_size: int = 1
subroutine_return: int = -1

while window_size < len(array) and subroutine_return == -1:
subroutine_return = subroutine(array, window_size, s)
window_size += 1

return subroutine_return

from rich.console import Console
console = Console()


console.print(ssgs(testcase1, testcase1s),
ssgs(testcase2, testcase2s),
ssgs(testcase3, testcase3s),
ssgs([1, 2, 10, 3, 4, 5, 6, 7, 8], 17))

Output
2 3 1 3


### Time complexity

$$O(N)$$ work for each size of the window and at most $$N$$ is the windows size. So $$N*O(N) = O(N^2)$$

### Better Optimized approach

• First we add up the elements of the array from start until we get the sum at least the target
• This is the first window size from the array that at least sums upto the target, so we remember the length
• We will remember the length of the window if we find a smaller window than this that sums at least the target.

Coming soon

Room for more understanding

...

## Longest Substring with K Distinct Characters

### Problem statement

Given a string, find the length of the longest substring in it with no more than K distinct characters.

Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".