Sliding Window

I can't see the whole picture at once, only what's right in front of me. Let me slide my window of focus and see what I can find.

You're monitoring a high-frequency stream of network requests to detect a security threat. How would you find the shortest, most intense spike of traffic that exceeds a critical threshold, without constantly re-scanning the entire data history?

Here is a problem that demonstrates how a dynamic sliding window works. Try it out before reading on.

Problem: Longest Substring Without Repeating Characters: (LeetCode Link) : Given a string, find the length of the longest substring without repeating characters. 💡 Hint

The brute-force solution would be to check every possible substring, which would take $O(n^2)$ time. The optimal solution here is to use the Sliding Window technique. You maintain a "window" that slides the data. Instead of re-computing for each position, we update only the element that is being added or removed from the window. This way, we can reduce the time complexity to $O(n)$ .

...

The General Template

Read the below template, re-read it multiple times, until you can write it from memory. This is the most important part of the Sliding Window pattern. When you get a sliding window problem, you should never spend time thinking about how to implement it. Instead, you should just write the template and fill in the blanks.

left = 0
# 1. Initialize state...

for right = 1 to n
    # 2. Shrink window until your condition is valid again
    while not condition_valid:
        # Remove arr[left] from window
        left += 1

    # 3. update the state to include arr[right]
    
    # 4. Update result based on the current valid window

# We have the result here

Walkthrough: Solving "Longest Substring Without Repeating Characters"

Let's apply sliding to the problem of finding the longest substring without repeating characters.

Initialize: left=0, max_length=0, and a set to track characters in the current window.
Expand the window: Start a for loop with right iterating through the string. Each iteration represents adding a new character to the window.
- If s.charAt(right) is already in the set, we can't expand the window. So remove characters one by one from the left until the character at s.charAt(right) is not in the set.
- Add s.charAt(right) to the set.
Update the result: Now that we have a valid window, we calculate its length (right - left + 1) and update max_length if this length is greater than the previous maximum.

def length_of_longest_substring(s):
    left = 0
    # 1. Initialize state...
    max_length = 0
    char_set = set() # Use a set to track characters in the current window

    for right in range(len(s)):
        # 2. If the current character is already in the set, shrink the window from the left
        while s[right] in char_set:
            char_set.remove(s[left]) # Remove leftmost character from window
            left += 1

        # 3. Add current character to set
        char_set.add(s[right])

        # 4. Update the maximum length found so far
        max_length = max(max_length, right - left + 1)

    return max_length

import java.util.HashSet;
import java.util.Set;

public int lengthOfLongestSubstring(String s) {
    int left = 0;
    // 1. Initialize state...
    int maxLength = 0;
    Set<Character> charSet = new HashSet<>(); // Use a set to track characters in the current window

    for (int right = 0; right < s.length(); right++) {
        // 2. If the current character is already in the set, shrink the window from the left
        while (charSet.contains(s.charAt(right))) {
            charSet.remove(s.charAt(left)); // Remove leftmost character from window
            left++;
        }

        // 3. Add current character to set
        charSet.add(s.charAt(right));

        // 4. Update the maximum length found so far
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

#include <string>
#include <unordered_set>
#include <algorithm>

int lengthOfLongestSubstring(const std::string& s) {
    int left = 0;
    // 1. Initialize state...
    int maxLength = 0;
    std::unordered_set<char> charSet; // Use a set to track characters in the current window

    for (int right = 0; right < s.length(); right++) {
        // 2. If the current character is already in the set, shrink the window from the left
        while (charSet.count(s[right])) {
            charSet.erase(s[left]); // Remove leftmost character from window
            left++;
        }

        // 3. Add current character to set
        charSet.insert(s[right]);

        // 4. Update the maximum length found so far
        maxLength = std::max(maxLength, right - left + 1);
    }

    return maxLength;
}

Complexity Analysis

Time Complexity: $O(N)$ Although there is a nested while loop, each character is added to and removed from the window at most once. Therefore, the left and right pointers each traverse the string only once.

Space Complexity: $O(N)$ In the worst case, we might store all characters in the set if all characters are unique.

Variation: Static Sliding Window

Here is another problem to try out.

Problem: Maximum Sum Subarray of Size K: (LeetCode Link) : Given an array of integers and a number k, find the maximum sum of a subarray of size k. 💡 Hint

What would be the condition violation here? You can think of this problem in two ways:

Fixed-Size Window: Initialize a window of size k and then move both pointers together, maintaining the sum of the current window.
Dynamic-Size Window (I recommend this): Think of this as a dynamic sliding window where the condition is the size of the window. You expand the window until it reaches size k, then you shrink it from the left to maintain the size. This way you can use a single template for both fixed and dynamic sliding windows.

def max_sum_subarray(arr, k):
    left = 0
    # 1. Initialize state...
    max_sum = 0
    window_sum = 0

    for right in range(len(arr)):
        # 2. Shrink window until the window size <= k
        if right - left + 1 > k:
            window_sum -= arr[left]
            left += 1

        # 3. Update the sum of the current window
        window_sum += arr[right]

        # 4. Update the maximum sum found so far
        if right - left + 1 == k:
            max_sum = max(max_sum, window_sum)
    return max_sum

public int maxSumSubarray(int[] arr, int k) {
    int left = 0;
    // 1. Initialize state...
    int maxSum = 0;
    int windowSum = 0;

    for (int right = 0; right < arr.length; right++) {
        // 2. Shrink window until the window size <= k
        if (right - left + 1 > k) {
            windowSum -= arr[left];
            left++;
        }

        // 3. Update the sum of the current window
        windowSum += arr[right];

        // 4. Update the maximum sum found so far
        if (right - left + 1 == k) {
            maxSum = Math.max(maxSum, windowSum);
        }
    }
    return maxSum;
}

int maxSumSubarray(const std::vector<int>& arr, int k) {
    int left = 0;
    // 1. Initialize state...
    int maxSum = 0;
    int windowSum = 0;

    for (int right = 0; right < arr.size(); right++) {
        // 2. Shrink window until the window size <= k
        if (right - left + 1 > k) {
            windowSum -= arr[left];
            left++;
        }

        // 3. Update the sum of the current window
        windowSum += arr[right];

        // 4. Update the maximum sum found so far
        if (right - left + 1 == k) {
            maxSum = std::max(maxSum, windowSum);
        }
    }
    return maxSum;
}

The General Template

Walkthrough: Solving "Longest Substring Without Repeating Characters"

Complexity Analysis

Variation: Static Sliding Window

More Problems & Variations