Sliding Window Technique for Subarray and Substring Problems

The Sliding Window: A New Perspective on Pointers

The sliding window pattern is your go-to tool for problems that ask for something optimal (like the longest, shortest, or maximum-sum) over a contiguous block of elements. Think of it as a scanner moving across the data. Instead of re-computing values for every possible subarray from scratch, you intelligently update the window's state as it slides.

To get a better feel for this idea, the following video offers a great high-level introduction.

As the video mentions, sliding windows come in two main flavors. Recognizing which type a problem requires is the first step toward a solution. Let's start with the more straightforward variant.

1. The Fixed-Size Sliding Window

This pattern applies when the problem statement explicitly defines the window's length, k. Your task is to find the best window of this fixed size as it slides across the array.

The core principle is efficiency. To move the window one step to the right, you don't recalculate everything. You simply:

1. Add the new element that enters the window on the right.
2. Subtract the old element that falls out of the window on the left.

This maintains a running calculation for the window's state in constant time per step.

Example: Maximum Sum Subarray of Size K

This is the classic fixed-size window problem. Given an array of integers nums and a size k, find the maximum sum of any contiguous subarray of size k.

1. Clarify & Plan

• Brute-Force: You could generate every subarray of size k and calculate its sum. This would involve a nested loop structure, leading to an $O(n\cdot k)$ time complexity. For large inputs, this is too slow.
• Optimized Plan (Sliding Window): We can achieve this in a single pass, making it $O(n)$.
  1. Calculate the sum of the initial window (the first k elements). This is our initial max_sum.
  2. Iterate from the k-th element to the end of the array. In each step, this element is our new right edge.
  3. Update the window's sum by adding the new element and subtracting the element that just left the window's left edge.
  4. Compare this new window sum with max_sum and update max_sum if it's larger.
  5. Return max_sum after the loop.

2. Implement & Verify

The following video provides a detailed walkthrough of this exact logic and its implementation.

Here is a clean Python implementation of the fixed-size sliding window pattern for this problem:

def max_sum_subarray(nums: list[int], k: int) -> float:



    # Calculate the sum of the first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    



    # Slide the window from k to the end of the array
    for i in range(k, len(nums)):



        # Add the new element and remove the leftmost element
        window_sum = window_sum + nums[i] - nums[i - k]



        # Update the maximum sum found so far
        max_sum = max(max_sum, window_sum)
        
    return max_sum

This pattern is direct and powerful. When you see a problem asking for an aggregate (sum, average, etc.) over a subarray of a specific size k, think "fixed-size sliding window."

2. The Variable-Size Sliding Window

This is where the pattern becomes more dynamic and versatile. Here, the window size is not fixed. Instead, it expands and contracts based on a certain condition. You typically use this for problems asking for the longest or shortest subarray/substring that satisfies a given property.

The general logic is:

1. Expand: Always move the right pointer to grow the window.
2. Check Validity: After expanding, check if the current window is still valid according to the problem's constraints.
3. Contract: If the window is invalid, move the left pointer to shrink the window until it becomes valid again.
4. Update Result: At each valid step, update your answer (e.g., the maximum length seen so far).

A hash map (or dictionary in Python) is often indispensable here for tracking the state of the window, such as character counts or frequencies.

Example: Longest Substring Without Repeating Characters (LeetCode 3)

Given a string s, find the length of the longest substring without repeating characters.

1. Clarify & Plan

• Problem: We need the length of the longest contiguous block of characters where every character is unique.
• Condition: The window is "valid" if it contains no duplicate characters. It's "invalid" as soon as a duplicate is introduced.
• Plan (Variable-Size Window):
  1. Use two pointers, left and right, both starting at index 0.
  2. Use a hash set char_set to store the characters currently in our window.
  3. Iterate with the right pointer to expand the window.
  4. At each step, check if s[right] is already in char_set.
  5. If it is (window becomes invalid), enter a while loop. Inside, remove s[left] from the set and increment left until the duplicate is gone and the window is valid again.
  6. Once the window is valid, add s[right] to the char_set.
  7. Calculate the current window's length (right - left + 1) and update the max_length.

2. Implement & Verify

The same video from Greg Hogg explains this dynamic approach clearly.

The code reflects this expand-and-contract logic perfectly.

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):



        # Contract: If the new character is already in the window,
        # shrink the window from the left until the duplicate is removed.
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
            



        # Expand: Add the new character to the window.
        char_set.add(s[right])
        



        # Update the result with the length of the current valid window.
        max_length = max(max_length, right - left + 1)
        
    return max_length

This dynamic resizing is the heart of the variable-size sliding window. It efficiently explores all valid subarrays/substrings without the overhead of a brute-force approach.

To solidify your understanding, let's review the core concepts in a written guide.

A Glimpse into Advanced Sliding Windows

The sliding window pattern can be combined with other data structures to solve even harder problems. Consider this famous LeetCode "Hard" problem:

A naive approach would be $O(n\cdot k)$, as you'd need to scan each window of size k to find its maximum. However, by using a specialized data structure called a monotonic queue (specifically, a deque in Python), we can track the maximum of the current window in $O(1)$ amortized time for each slide, bringing the total time complexity back down to an optimal $O(n)$. We will explore queues and deques in Module 3, but it's valuable to see now how these fundamental patterns serve as building blocks for more complex algorithms.

Conclusion

In this lesson, you've added the versatile sliding window pattern to your algorithmic toolkit. This technique is fundamental for solving a wide array of interview problems efficiently.

Key Takeaways:

• Sliding Window is the optimal pattern for problems involving contiguous subarrays or substrings.
• Fixed-Size Window: Used when the problem specifies a window of size k. The logic is to slide the window by adding one element and removing one element at each step.
• Variable-Size Window: Used to find the longest/shortest subarray satisfying a condition. The window expands from the right and contracts from the left when the condition is violated. A hash map or set is often used to track the window's state.
• Both patterns reduce time complexity from polynomial (e.g., $O(n^2)$) to linear ($O(n)$), a critical optimization in coding interviews.

In our next lesson, we will cover the prefix sum technique. While sliding windows are perfect for finding optimal contiguous segments, prefix sums excel at answering queries about the sum of fixed ranges within an array, offering yet another way to optimize array-based problems.