Sliding Window Patterns

From Brute Force to Linear Time

Many problems involving contiguous subarrays or substrings seem to demand nested loops. Consider this: find the maximum sum of any contiguous subarray of size 3 in an array.

The brute-force way is to generate every possible subarray of size 3, calculate its sum, and track the maximum sum found. It's straightforward but inefficient.

def find_max_sum_brute_force(arr):
    max_sum = -float('inf')
    # The outer loop determines the starting point of the subarray
    for i in range(len(arr) - 2):
        current_sum = 0
        # The inner loop sums the 3 elements
        for j in range(i, i + 3):
            current_sum += arr[j]
        max_sum = max(max_sum, current_sum)
    return max_sum

my_array = [2, 1, 5, 1, 3, 2]
print(find_max_sum_brute_force(my_array)) # Output: 9

This nested loop structure results in a time complexity of roughly $O(n \times k)$ , where $n$ is the array length and $k$ is the subarray size. If $k$ is proportional to $n$ , this approaches $O(n^2)$ . We can do much better.

The Sliding Window technique transforms this into a single pass, achieving a linear $O(n)$ time complexity. Instead of recalculating the sum for each subarray, we slide a "window" across the array, updating the sum incrementally.

Fixed-Size Windows

The simplest form of this pattern uses a window of a fixed size. For our maximum sum problem, the window size is constant at 3.

Here's the logic:

Calculate the sum of the initial window (the first 3 elements).
Slide the window one position to the right. To get the new sum, subtract the element that's now outside the window and add the new element that just entered.
Repeat until the window reaches the end of the array, updating the maximum sum at each step.

This approach requires only one pass through the array.

def find_max_sum_sliding_window(arr, k):
    if len(arr) < k:
        return 0

    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window from the k-th element to the end
    for i in range(k, len(arr)):
        # Subtract the element that's left behind
        # Add the new element that enters the window
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

my_array = [2, 1, 5, 1, 3, 2]
print(find_max_sum_sliding_window(my_array, 3)) # Output: 9

Variable-Size Windows

Things get more interesting when the window size isn't fixed. Here, the window expands and contracts based on certain conditions. This pattern is common in problems like "find the longest substring with no more than K distinct characters."

The core mechanism uses two pointers, left and right, which define the boundaries of the current window.

Expansion: The right pointer always moves forward, one element at a time, expanding the window.
Contraction: The left pointer only moves forward when a condition is violated (e.g., we have more than K distinct characters). It moves to shrink the window until the condition is met again.

The pattern is: expand the window from the right, and if the window becomes invalid, shrink it from the left until it's valid again.

Let's tackle a classic problem: find the length of the longest substring without repeating characters.

Here, our "window" must contain only unique characters. When we expand the window and encounter a character that's already inside, the window becomes invalid. To fix it, we must shrink the window from the left until the duplicate character is removed.

def longest_substring_no_repeats(s):
    char_index_map = {}
    max_length = 0
    left = 0

    # The 'right' pointer is the loop variable
    for right, char in enumerate(s):
        # If the character is already in the window AND its last occurrence
        # is within the current window's bounds (>= left).
        if char in char_index_map and char_index_map[char] >= left:
            # The window is invalid. Shrink it by moving the left pointer
            # to the position right after the previous occurrence of 'char'.
            left = char_index_map[char] + 1

        # Update the character's last seen index
        char_index_map[char] = right

        # Calculate the current window's length and update the max
        current_length = right - left + 1
        max_length = max(max_length, current_length)

    return max_length

print(longest_substring_no_repeats("abcabcbb")) # Output: 3, for "abc"
print(longest_substring_no_repeats("pwwkew")) # Output: 3, for "wke"

Notice how we only iterate through the string once with the right pointer. The left pointer also only moves forward. This ensures each element is processed at most twice (once by right, once by left), giving us a time complexity of $O(n)$ .

The trade-off is space. We use a hash map to store character information, which could take up to $O(m)$ space, where $m$ is the number of unique characters in the input string. For a standard ASCII character set, this is effectively constant space, $O(1)$ , because $m$ is limited.

Ready to test your understanding?

Quiz Questions 1/5

What is the primary advantage of using the Sliding Window technique over a brute-force nested loop approach for problems involving contiguous subarrays?

Quiz Questions 2/5

You are tasked with finding the maximum sum of a contiguous subarray of size k=4 in the array [1, 4, 2, 10, 23, 3, 1, 0, 20]. The current window is [4, 2, 10, 23], and its sum is 39. What is the sum of the next window?

The Sliding Window is a powerful pattern for optimizing problems on contiguous data. By thinking in terms of an expanding and contracting window, you can often turn a slow, brute-force solution into a fast, linear-time one.

One Week Python LeetCode Sprint

One Week Python LeetCode Sprint

Sliding Window Patterns

From Brute Force to Linear Time

Fixed-Size Windows

Variable-Size Windows