Sliding Window

The Sliding Window technique is a powerful algorithmic strategy used to solve problems that involve finding a subset of data in a contiguous block within an array or list. It optimizes brute force approaches by reducing redundant calculations, making it ideal for problems related to subarrays, substrings, or ranges.

Instead of recalculating the solution from scratch for each subset (like brute force), the window slides across the data structure, updating only the relevant information. This technique is especially effective in problems that require keeping track of a fixed-size window or dynamically adjusting the window size to satisfy certain conditions.

Common Use Cases:

• Maximum or minimum sum of a subarray of fixed size
• Longest substring with specific properties (like all unique characters)
• Counting occurrences of a pattern in a string

How to Identify this Pattern in a Given Coding Question

You can recognize when the Sliding Window technique might be applicable by identifying the following key indicators:

• Subarrays/Substrings: The problem asks for the largest, smallest, or any condition (e.g., maximum sum) related to a subarray or substring.
• Fixed or Variable Window Size: The problem either specifies a fixed window size (e.g., “find the maximum sum of a subarray of length k”) or asks for the largest window that satisfies a certain condition (e.g., “find the longest substring with distinct characters”).
• Contiguous Data: The problem requires dealing with consecutive elements, either in an array, list, or string.

Example question types include: Find the maximum sum of k consecutive elements in an array. Find the longest substring with at most k distinct characters.

Variances of the Sliding Window Technique

There are two primary types of Sliding Window techniques:

1. Fixed Size Window: The size of the window remains constant throughout the process. You simply slide the window from left to right across the array, updating the current sum or other relevant metrics.

• Example: Finding the maximum sum of a subarray of size k.

1. Dynamic/Variable Size Window: The size of the window changes based on a certain condition, typically expanding or contracting as needed to meet the problem’s criteria.

• Example: Finding the longest substring with all unique characters.

Tricks to Keep in Mind

• Efficient Sliding: For fixed window sizes, always remember that you don’t need to recalculate the sum (or other values) from scratch when moving the window. Simply subtract the element that goes out of the window and add the new element that comes in.
• Two Pointers for Variable Windows: When dealing with variable window sizes, use two pointers (left and right) to dynamically adjust the window. Increment the right pointer to expand the window, and increment the left pointer to contract the window as necessary.
• Edge Cases: Consider edge cases like when the input array is smaller than the window size or when no valid subarray/substring is found.
• HashMaps/Arrays for Condition Checking: For problems involving conditions like “at most k distinct characters”, using a hashmap (or array for simple cases) can help efficiently track the frequency of elements in the current window.

Common Coding Questions

Question 1: Maximum Sum of Subarray of Size k (Fixed Window Size)

from typing import List

class SlidingWindowFixed:
    def max_sum_subarray(self, nums: List[int], k: int) -> int:
        if len(nums) < k:
            return -1  # Invalid case if array length is less than window size
        max_sum = curr_sum = sum(nums[:k])
        for i in range(k, len(nums)):
            curr_sum += nums[i] - nums[i - k]
            max_sum = max(max_sum, curr_sum)
        return max_sum

# Example Usage
nums = [2, 1, 5, 1, 3, 2]
k = 3
solution = SlidingWindowFixed()
print(solution.max_sum_subarray(nums, k))  # Output: 9 (5 + 1 + 3)

Question 2: Longest Substring with At Most k Distinct Characters (Variable Window Size)

class SlidingWindowVariable:
    def longest_substring_k_distinct(self, s: str, k: int) -> int:
        if k == 0 or not s:
            return 0
        
        char_count = {}
        left = 0
        max_length = 0
        for right in range(len(s)):
            char = s[right]
            char_count[char] = char_count.get(char, 0) + 1
            
            while len(char_count) > k:
                left_char = s[left]
                char_count[left_char] -= 1
                if char_count[left_char] == 0:
                    del char_count[left_char]
                left += 1
            
            max_length = max(max_length, right - left + 1)
        return max_length

# Example Usage
s = "eceba"
k = 2
solution = SlidingWindowVariable()
print(solution.longest_substring_k_distinct(s, k))  # Output: 3 ("ece")

Question 3: Smallest Subarray with a Sum Greater Than S (Variable Window Size)

class SlidingWindowMinSize:
    def min_subarray_length(self, nums: List[int], target: int) -> int:
        n = len(nums)
        min_length = float('inf')
        current_sum = 0
        left = 0
        for right in range(n):
            current_sum += nums[right]
            while current_sum >= target:
                min_length = min(min_length, right - left + 1)
                current_sum -= nums[left]
                left += 1
        
        return min_length if min_length != float('inf') else 0

# Example Usage
nums = [2, 1, 5, 2, 8]
target = 7
solution = SlidingWindowMinSize()
print(solution.min_subarray_length(nums, target))  # Output: 1 ([8] is the smallest subarray)