5  Sliding Window Technique

5.1 Sliding Window Pattern

The sliding window technique is used to perform a required operation on a specific window size of a given array or linked list, such as finding the longest subarray with a given sum.

5.1.1 When to Use

• When dealing with arrays or strings
• When you need to find a subarray or substring that meets certain criteria
• When the problem requires finding something among all contiguous subarrays of a given size

5.1.2 Common Problems

1. Maximum Sum Subarray of Size K
2. Smallest Subarray with a Given Sum
3. Longest Substring with K Distinct Characters
4. String Anagrams
5. Maximum Number of Vowels in a Substring

5.1.3 Example: Maximum Sum Subarray of Size K

def max_subarray_sum(arr, k):
    max_sum = window_sum = sum(arr[:k])
    window_start = 0
    
    for window_end in range(k, len(arr)):
        window_sum = window_sum - arr[window_start] + arr[window_end]
        max_sum = max(max_sum, window_sum)
        window_start += 1
        
    return max_sum

5.1.4 Time Complexity

• O(n) time | O(1) space, where n is the number of elements in the array

5.1.5 Types of Sliding Window

1. Fixed Size Window: Window size remains constant
2. Dynamic Size Window: Window size changes based on certain conditions

5.1.6 Practice Problems

1. Maximum Subarray
2. Longest Substring Without Repeating Characters
3. Fruit Into Baskets

5.1.7 Tips

1. Use hash maps to keep track of elements in the current window
2. The sliding window approach is often used with the two pointers technique
3. For problems with negative numbers, the sliding window approach might not be directly applicable