Sliding Window Technique: Substring and Subarray Problems

1. What is the Sliding Window Technique?

At its core, the sliding window technique is an optimization that avoids the redundant work of a brute-force approach. A naive solution to a subarray problem might involve nested loops to check every single possible subarray, often resulting in an O(n²) or even O(n³) time complexity.

The sliding window approach reduces this to O(n) time. It maintains a "window" (a sub-section of the array or string) using two pointers, often called left and right or start and end. The right pointer expands the window, and the left pointer contracts it. By intelligently sliding this window over the data, we only need to process each element a constant number of times.

There are two primary types of sliding windows, and knowing which one to use is key to solving problems effectively:

1. Fixed-Length Sliding Window: Used when the problem specifies a subarray or substring of a fixed size, k.
2. Variable-Length Sliding Window: Used when the problem asks for the longest or shortest subarray that satisfies a given condition.

Let's dive into each type.

2. Fixed-Length Sliding Window

This is the more straightforward variant. You use it when the problem statement explicitly gives you the window size, k. The core idea is to maintain a window of exactly size k and slide it across the array one step at a time.

The Logic:

1. First, build the initial window by processing the first k elements.
2. Calculate the desired value (e.g., sum, average) for this initial window.
3. Then, iterate from the k-th element to the end of the array. In each step:
   • Expand: Add the new element (at the right end) to your window's state.
   • Contract: Remove the element that is falling out of the window (at the left end) from your state.
   • Update your overall result (e.g., the maximum sum found so far).

This "add one, subtract one" process is what makes the algorithm so efficient.

Code and Complexity

As you saw in the video, the implementation is clean and efficient. Here's a general template for the fixed-length pattern.

def fixed_length_sliding_window(arr, k):



    # Initialize variables to track window state and overall result
    current_window_sum = 0
    max_sum = float('-inf')
    



    # Initialize pointers
    left = 0
    
    for right in range(len(arr)):



        # Expand the window by adding the right element
        current_window_sum += arr[right]
        



        # Once the window reaches size k, start sliding
        if right >= k - 1:



            # Update the result with the current window's state
            max_sum = max(max_sum, current_window_sum)
            



            # Contract the window by removing the left element
            current_window_sum -= arr[left]
            left += 1
            
    return max_sum

• Time Complexity: O(n), because each element is visited exactly once by the right pointer and once by the left pointer.
• Space Complexity: O(1), as we only use a few variables to store the state.

For additional reference, the article Fixed-Length Sliding Window from Hello Interview also provides a great template and explanation.

3. Variable-Length Sliding Window

This pattern is more dynamic and addresses a broader class of problems, making it very common in interviews. You use it when you need to find the longest or shortest contiguous subarray that satisfies some property.

Here, the window size is not fixed. It grows and shrinks based on whether a certain condition is met.

The Logic:
The core of this pattern is a while loop nested inside a for loop, which may seem like O(n²) but is actually O(n).

1. Initialize left = 0 and a data structure to track the window's state (e.g., a hash map for character counts, a set for unique elements, a variable for the sum).
2. Iterate through the array with a right pointer from 0 to n-1.
3. Expand: At each step, add the element arr[right] to your window's state.
4. Check and Contract: After expanding, check if the window's state is invalid (e.g., sum is too large, more than k distinct characters).
   • If it is, enter a while loop to contract the window from the left.
   • In the while loop, remove arr[left] from the window's state and increment left.
   • Continue contracting until the window becomes valid again.
5. After any necessary contractions, the window is guaranteed to be valid. Update your result (e.g., max_length = max(max_length, right - left + 1)).

Let's look at two classic examples to see this in action.

Example 1: Longest Substring Without Repeating Characters

This problem asks for the longest substring with all unique characters. The "validity" condition is that the window must not contain any duplicate characters.

Example 2: Minimum Size Subarray Sum

This problem asks for the shortest contiguous subarray whose sum is greater than or equal to a target. The "validity" condition is current_sum >= target. The logic is slightly different because we want to shrink the window as soon as it becomes valid to find the minimum length.

Code, Complexity, and Template

The key takeaway is that although there's a nested loop structure, the time complexity remains O(n). This is because the left and right pointers each traverse the array only once from left to right.

The Hello Interview article on this topic provides an excellent step-by-step motivation and a clean template to internalize.

Conclusion

Today, we added the powerful sliding window technique to your algorithmic toolkit. It's a fundamental pattern for efficiently solving a wide range of subarray and substring problems that might otherwise require a brute-force O(n²) solution.

Key Takeaways:

• Core Idea: Use two pointers (left, right) to maintain a "window" over the data, avoiding re-computation by sliding the window instead of rebuilding it. The result is an optimal O(n) time complexity.
• Fixed-Length Window: Use when the problem specifies a subarray of size k. The logic is to slide a window of constant size, adding one new element and removing one old element at each step.
• Variable-Length Window: Use when searching for the longest or shortest subarray that meets a condition. The logic is to expand the window with the right pointer and contract it with the left pointer whenever a certain validity condition is violated (or met, in minimization problems).

Preview of the Next Lesson

Having covered 1D arrays extensively, we will now move into two dimensions. In the next lesson, we will tackle matrix traversal and in-place manipulation problems. We will explore classic algorithms like spiral traversal and rotating a matrix, which are common questions in FAANG interviews and require a strong command of index manipulation and boundary conditions.