# Coding Patterns: Sliding Window

In **Coding Patterns** series, we will try to *recognize* common patterns *underlying* behind each algorithm question, using real examples from Leetcode.

First, we will introduce Sliding Window pattern which is very useful to solve problems in which you are asked to find the *longest/shortest string*, *subarray*, or a *desired value* which you need to calculate from subarrays.

## Problem: Maximum Average Subarray

**LeetCode 643 - Maximum Average Subarray I** [*easy*]

Given an array consisting of ** n** integers, find the

*contiguous subarray*of given length

**that has the maximum average value. And you need to output the**

`k`

*maximum average value*.

**Example:**

```
Input: [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
```

### Brute Force Solution

```
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
max_average = 0.0
for i in range(len(nums) - k + 1):
_sum = 0.0 # find sum of next k elements
for j in range(i, i + k):
_sum += nums[j]
average = _sum / k # calculate the average of selected k elements
max_average = max(max_average, average) # update max_average
if len(nums) == 1: # if there is only 1 element in nums
return average
return max_average
```

**Time Complexity**: **O(N*k)** where ** N** is the number of elements in the input array.

This solution exceeds the time limit defined by Leetcode and is **not accepted**.

If we check our example array again: `[1, 12, -5, -6, 50, 3]`

for `k = 4`

, there are 3 *overlapping* elements between subarrays `[1, 12, -5, -6]`

and `[12, -5, -6, 50]`

. Can we somehow reuse the `_sum`

we have calculated for the *overlapping* elements to make our solution more efficient?

### Sliding Window Solution

To be able to reuse the `_sum`

from the previous *subarray*, we will **subtract** the element *going out* of the window and *add* the element now being **included** in the sliding window.

```
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
average = []
_sum, start = 0, 0
for end in range(len(nums)):
_sum += nums[end] # add the next element
if end >= k - 1:
average.append(_sum / k) # calculate the average
_sum -= nums[start] # subtract the element going out
start += 1 # slide the window
return max(average)
```

**Time Complexity**: **O(N)** where ** N** is the number of elements in the input array.

## How to identify?

So we want to be able to identify the problems that sliding window pattern works.

- The problem involves a data structure that is ordered and iterable like
*arrays*,*strings*, etc. - The problem is asking to find a subrange in an
*array*/*string*, contiguous*longest*,*shortest*,*average*or*target*value. - There is an apparent
*naive*or brute force solution that runs in**O(N**,^{2})**O(2**or some other large time complexity.^{N})

The amazing thing about sliding window problems is that most of the time they can be solved in **O(N)** time and **O(1)** space complexity.

## Similar LeetCode Problems

- LeetCode 3 - Longest Substring Without Repeating Characters [
*medium*] - LeetCode 30 - Substring with Concatenation of All Words [
*hard*] - LeetCode 76 - Minimum Window Substring [
*hard*] - LeetCode 209 - Minimum Size Subarray Sum [
*medium*] - LeetCode 424 - Longest Repeating Character Replacement [
*medium*] - LeetCode 438 - Find All Anagrams in a String [
*medium*] - LeetCode 567 - Permutation in String [
*medium*] - LeetCode 904 - Fruit Into Baskets [
*medium*] - LeetCode 1004 - Max Consecutive Ones III [
*medium*]