# Sliding Window
## Introduction

Working with pointers reduces the complexity of O(n^2) to O(n).

Average of subarrays size K:

# Brute force (O(n^2))
def average_of_subarrays_of_size_k_BF(k: int, arr: list):
    result = []
    # Iterations
    for ix, element in enumerate(range(len(arr) - k + 1)):
        result.append((sum(arr[ix: k + ix]) / k))
    
    return result


# Optimal (O(n))
def average_of_subarrays_of_size_k_OPT(k: int, arr: list):
    result = []
    # Insert first result
    current_sum = round((sum(arr[:k]) / 5), 1)
    result.append(current_sum)
    
    # Create sliding window pointers
    start_point = 0
    end_point = 5
    
    # Iterations
    for it in range(1, len(arr) - k + 1):
        current_sum = current_sum - (arr[start_point] / k) + (arr[end_point] / k)
        result.append(round(current_sum, 1))
        start_point = start_point + 1
        end_point = end_point + 1

    return result

Max sum of subarrays size K:

# Optimal (O(n))
def max_sum_of_subarrays_of_size_k_OPT(k: int, arr: list):
    # Insert first result
    max_sum = round(sum(arr[:k]), 1)
    temp_sum = max_sum
    
    # Create sliding window pointers
    start_point = 0
    end_point = k
    
    # Iterations
    for it in range(1, len(arr) - k + 1):       
        temp_sum = temp_sum - arr[start_point] + arr[end_point]       
        max_sum = temp_sum if temp_sum > max_sum else max_sum
        
        start_point = start_point + 1
        end_point = end_point + 1

    return max_sum

Smallest subarray for given sum:

# Suboptimal (O(n^2))
def sum_of_subarrays_of_size_k_BF(k: int, s: int, arr: list):
    # Insert first result
    max_sum = round(sum(arr[:k]), 1)
    current_slice = arr[:k]
    # return result immediately if S is found
    if (max_sum >= s): return max_sum, current_slice
    
    # Create sliding window pointers
    temp_sum = max_sum
    start_point = 0
    end_point = k
    
    # Iterations
    for it in range(1, len(arr) - k + 1):    
        current_slice = arr[start_point+ 1:end_point + 1 ]   
        temp_sum = temp_sum - arr[start_point] + arr[end_point]       
        max_sum = temp_sum if temp_sum > max_sum else max_sum
        
        start_point = start_point + 1
        end_point = end_point + 1
        current_slice = arr[start_point:end_point] 
        
        if (max_sum >= s): return max_sum, current_slice

    return max_sum, current_slice


def smallest_subarray_with_given_sum_SUB_OPT(s: int, arr: list):
    for sub_array_size in range(1, len(arr)):
        max_sum, min_slice = sum_of_subarrays_of_size_k_BF(sub_array_size, s, arr)
        if (max_sum >= s): 
            print(min_slice)
            return min_slice
    return -1

# Optimal (O(n))
def smallest_subarray_with_given_sum(s: int, arr: list):
    # Create sliding window pointers
    start_point = 0
    end_point = 0
    current_sum = sum(arr[start_point:end_point + 1])
    min_sub_len = -1

    while start_point <= len(arr) and end_point <= len(arr):
        # Determine sub array
        if current_sum >= s:
            current_sum = current_sum - arr[start_point]
            start_point = start_point + 1
        elif current_sum < s:
            end_point = end_point + 1
            if (end_point < len(arr)):
                current_sum = current_sum + arr[end_point]
        
        # Calculate min length of sub array   
        if current_sum >= s:
            curr_sub_len = end_point - start_point + 1
            min_sub_len = curr_sub_len if (min_sub_len == -1 or min_sub_len > curr_sub_len) else min_sub_len
     
    return min_sub_len

Longest substring with maximum K Distinct Characters: