Sliding Window

The sliding window is a technique used to efficiently solve problems involving subarrays or substrings in arrays, strings, or similar ordered data structures. It helps when you need to examine a sequence of elements that form contiguous subsets.

When to use it

You can identify problems that can be solved with a sliding window if they meet one or more of these conditions:

1. You need to find or optimize over subarrays or substrings.
2. The problem involves contiguous elements.
3. You're asked to find a result in linear time ($O(n)$ complexity).

Why use it

Sliding window reduces unnecessary calculations by "sliding" over the data in a single pass. Instead of recalculating the whole array or substring for each step, you update only the part of the window that changes, improving efficiency to $O(n)$.

How it works

The sliding window either grows, shrinks or remains a constant size based on the problem’s requirements. You slide the window one step at a time through the array or string.

Example 1: Fixed window size. Find the maximum sum of 3 contiguous elements in an array

Start by calculating the sum of the first 3 elements. Then slide the window one position to the right, subtract the element that falls out of the window and add the new one. Keep track of the maximum sum as you go.

Python
nums = [2, 1, 5, 1, 3, 2]
k = 3
max_sum = 0
current_sum = sum(nums[:k])  # sum of first window
for i in range(len(nums) - k):
    current_sum = current_sum - nums[i] + nums[i + k]  # slide window
    max_sum = max(max_sum, current_sum)

Example 2: Variable window size. Find the longest substring without repeating characters

Use a growing window that expands as long as the condition (no repeating characters) is met. If a repeat is encountered, shrink the window from the left until the condition is satisfied again.

Python
s = "abbcab"
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
    while s[right] in char_set:
        char_set.remove(s[left])
        left += 1
    char_set.add(s[right])
    max_len = max(max_len, right - left + 1)

Examples

1. Minimum window substring
   • Problem: Find the smallest window in a string that contains all characters of another string.
   • Approach: Use a variable window that expands to include all characters of the target and shrinks to find the minimal length.
2. Smallest subarray with a sum greater than or equal to S
   • Problem: Find the minimal length of a contiguous subarray whose sum is greater than or equal to S.
   • Approach: Expand the window to meet the sum requirement, and then shrink it to minimize the window size.
3. Longest substring with at most K distinct characters
   • Problem: Find the longest substring that contains at most K distinct characters.
   • Approach: Grow the window by adding characters and shrink it when the count of distinct characters exceeds K.