# Sliding window

## The Problem

Find subarray with given sum (Nonnegative Numbers): Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

```
Input: arr = [1, 4, 20, 3, 10, 5], n = 33
Output: Sum found between indexes 2 and 4
Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33
```

## The Solution

Since a continuous sub array is defined between a start and end index, we can find all subarray and calculate the sum.

```
for each start index
for each end index from start to length(arr)
calculate sum of arr[start:end]
```

The complexity will be quadratic. We can in fact do better. We observe that:

- At every start and end indexes, if the sum of arr[start:end] < n, we obviously need to move the end index forward.
- However, if the sum of arr[start:end] > n, then there is no point to calculate the sum of arr[start:end+1], arr[start:end+2], etc. What we should do is to move the start index forward.

For example, in the example above, we keep moving end index in step 1,2,3,4 since the sum is less than 33. At step 5 and 6, the sum is more than 33 and so we move the start index. Finally at step 7, we found the desired subarray. It seems that what we need is 2 variable “start” and “end” for this technique.

```
def find_subarray(nums, n):
current_sum = 0
start = 0
for end in range(len(nums)):
current_sum += nums[end]
while current_sum > n and start < end and start < len(nums):
current_sum -= nums[start]
start += 1
if current_sum == n:
return [start,end]
return None
```

```
func findSubarray(nums []int, n int) (int,int,bool) {
var start, end int
currentSum := 0
start = 0
for end, _ = range nums {
currentSum += nums[end]
for currentSum > n && start < end && start < len(nums) {
currentSum -= nums[start]
start += 1
}
if currentSum == n {
return start, end, true
}
}
return 0, 0, false
}
```

## The Analysis

Since the 2 pointers start and end move at most once, the worst complexity is O(2*n) = O(n). The challenge of this algorithm is to recognize the pattern and to implement the sliding window.

## String problems and implementation pattern

The implementation of sliding window is not always straightforward, especially when it is involved strings.

Let’s look at Leetcode 438 - Find All Anagrams in a String: Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

```
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```

The question is an application of sliding window technique at medium level.

```
def all_anagrams(s, p):
#define hashmap
hm = {}
for c in p:
hm[c] = hm.get(c, 0) + 1
# define counter, staer and end pointers
counter, start, end = 0, 0, 0
# result array
res = []
while end < len(s):
c = s[end]
if c in hm:
hm[c] -= 1
# counter per character, since we can have duplicates
if hm[c] == 0:
counter +=1
end += 1
#increase start when condition meets, different question will have different condition
while counter >= len(hm):
start_char = s[start]
if start_char in hm:
hm[start_char] = hm.get(start_char, 0) + 1
if hm[start_char] > 0:
counter -= 1
# update result here based on condition - we can put this anywhere in code depending on question
if counter == len(hm):
res.append(start)
start += 1
return res
```

Leetcode 567 - Permutation in String: Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

```
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
```

Example 2:

```
Input:s1= "ab" s2 = "eidboaoo"
Output: False
```

```
def checkInclusion(s1: str, s2: str):
if len(s1) > len(s2):
return False
s1_map = {}
for c in s1:
s1_map[c] = s1_map.get(c, 0) + 1
start, end, total = 0, 0, 0
while end < len(s2):
c = s2[end]
if c in s1_map:
if s1_map[c] > 0:
total += 1
s1_map[c] -= 1
end += 1
if total == len(s1):
return True
while end-start >= len(s1):
c = s2[start]
if c in s1_map:
if s1_map[c] >= 0:
total -= 1
s1_map[c] += 1
start += 1
return False
```

- Chocolate Distribution Problem
- Find maximum (or minimum) sum of a subarray of size k
- Find Minimum Length Sub Array With Sum K
- Fruits into Baskets
- Minimum Size Subarray Sum
- Max Consecutive Ones III
- K Empty Slots
- Count Number of Nice Subarrays

## Leave a comment