Sliding Window: Expand and Shrink

In our last lesson, we explored the fixed-size sliding window, a powerful technique for efficiently processing contiguous subarrays of a predetermined length. We saw how updating the window's state in constant time led to a significant performance gain. Now, we'll advance this concept to handle a more dynamic and common class of problems.

Today's learning outcome is to implement the expand-and-shrink logic for variable-size sliding windows to meet a condition. Unlike its fixed-size counterpart, this pattern doesn't rely on a given window length k. Instead, the window dynamically grows and contracts to find the optimal subarray—the longest or shortest—that satisfies a specific constraint. This expand-and-shrink mechanism is a cornerstone of efficient algorithm design for many array and string problems you'll encounter in coding interviews.

From Fixed to Variable: The Core Idea

With a fixed-size window, the motion is straightforward: the window slides one position at a time, maintaining its size. But what if a problem asks for the "longest subarray with a sum less than or equal to S" or the "shortest substring containing characters 'A', 'B', and 'C'"? Here, the optimal window size is unknown.

This is where the variable-size window shines. It operates based on a simple but powerful principle:

1. Expand: Grow the window by moving its right boundary.
2. Check: After each expansion, check if the window's state violates the given condition.
3. Shrink: If the condition is violated, shrink the window from its left boundary until it becomes valid again.

This continuous process of expanding and shrinking ensures that we efficiently explore all potential subarrays while maintaining the desired property. The logic is managed by two pointers, typically named left and right (or start and end), which mark the boundaries of our window.

The Expand-and-Shrink Mechanism in Action

Let's make this concrete. The core of the algorithm is a loop structure where the right pointer consistently moves forward, and an inner loop moves the left pointer only when necessary.

• Expansion Phase: A for loop iterates the right pointer from the beginning to the end of the array. In each step, we include the element array[right] into our window and update the window's state (e.g., add its value to a running sum, or increment its count in a hash map).

• Contraction Phase: Inside the for loop, a while loop checks if the window is currently invalid. If it is, we contract the window by moving the left pointer forward. As we do this, we must also reverse the changes made by the outgoing element array[left] to our window's state. This while loop continues until the window becomes valid again.

After each valid state is achieved (i.e., after the potential shrinking), we can update our answer (e.g., record the window's length if it's the longest we've seen so far).

Let's examine a classic problem that perfectly illustrates this dynamic: "Fruit Into Baskets" (LeetCode 904), which is equivalent to finding the longest subarray with at most two distinct elements.

As the article explains, the key is to stop "blowing it all up." Instead of restarting our subarray count from scratch, we intelligently shrink the window just enough to restore its validity (containing at most two types of fruit) and then continue expanding.

A General Template for Variable-Size Windows

This "expand-and-shrink" logic can be distilled into a reusable template. Your experience with LeetCode patterns will make this structure feel familiar, and it's a powerful tool to have.

def variable_sliding_window(arr):
    left = 0
    max_len = 0



    # Data structure to track the state of the window (e.g., hash map, set)
    window_state = {} 

    for right in range(len(arr)):



        # 1. EXPAND the window by adding the right element
        # Update window_state with arr[right]




        # 2. SHRINK the window if it's invalid
        while condition_is_violated(window_state):



            # Update window_state by removing arr[left]
            left += 1




        # 3. UPDATE the result. At this point, the window is always valid.
        max_len = max(max_len, right - left + 1)
    
    return max_len

This template is the blueprint. The main variations lie in the choice of window_state and the logic within condition_is_violated. Let's see it applied to another problem.

Example 2: Longest Substring Without Repeating Characters

This is another quintessential sliding window problem (LeetCode 3). The constraint is simple: the window (substring) must not contain any duplicate characters.

The window_state can be a hash set to keep track of characters currently in the window.

• Expand: Add s[right] to the set.
• Invalid Condition: A duplicate is found, meaning s[right] was already in the set.
• Shrink: Remove s[left] from the set and increment left until the duplicate s[right] is no longer present in the window.

The animation below shows this process for the string "abcabcbb".

The following video provides a very clear, step-by-step walkthrough of this exact logic.

Notice the code structure in the video perfectly matches our template: a for loop for the right pointer (expansion) and a while loop for the left pointer (contraction).

Adapting the Pattern: Minimum Window Substring

The expand-and-shrink pattern is versatile. It works for "longest" problems as well as "shortest" problems. Consider LeetCode 76: "Minimum Window Substring." Here, you are given a string S and a string T, and you must find the shortest substring in S that contains all characters of T.

The state management is more complex. You typically need two hash maps:

1. needs: To count the required characters from T.
2. window: To count the characters in your current sliding window.

The logic follows the same pattern:

• Expand: Move right and update the window map until the characters in your window satisfy the needs map.
• Shrink: Once you have a valid (but likely non-optimal) window, you shrink from the left to find the absolute minimum size that is still valid. Record this size if it's a new minimum. Continue shrinking until the window becomes invalid again, at which point the expansion phase resumes.

We will dive deeper into this specific problem type in a future lesson, but for now, it's useful to see how the core framework adapts.

Common Pitfalls and Complexity

As you've seen in your own practice, implementation details matter. Here are a few things to watch out for with this pattern:

• Window Size Calculation: Be consistent. If your pointers are inclusive, the window size is right - left + 1. An off-by-one error here is common.
• State Updates: When shrinking the window, you must correctly reverse the operation you performed when expanding. If you added to a count, you must subtract. If you deleted from a map's count, be sure to handle the case where the count becomes zero.
• Shrinking Loop: The shrinking logic must be a while loop, not an if statement. A single right pointer move might require shrinking the left pointer multiple times to restore validity.
• Time Complexity: You might see the nested for/while loops and think the complexity is $O(N^2)$. However, it is amortized $O(N)$. This is because each pointer, left and right, only moves forward through the array. Each element is visited at most twice—once by the right pointer and once by the left pointer. Therefore, the total number of operations is proportional to $2N$, which is $O(N)$.
• Space Complexity: The space complexity is determined by the data structure used to maintain the window_state. For problems involving character sets, it can be $O(K)$ where K is the size of the character set (e.g., 26 for lowercase English letters), which is effectively $O(1)$. In the worst case, it could be $O(N)$ if all elements in the input are unique and need to be stored.

Conclusion

In this lesson, we've moved beyond fixed-size windows to the more dynamic and powerful variable-size window. You've learned the fundamental expand-and-shrink logic that drives this pattern.

Key Takeaways:

• Variable-size sliding windows are ideal for finding the longest or shortest contiguous subarray that satisfies a given condition.
• The core mechanism is the expand-and-shrink logic, driven by a right pointer that always expands and a left pointer that contracts the window only when it becomes invalid.
• A general template using a for loop for expansion and a nested while loop for contraction can solve a wide variety of these problems.
• Despite the nested loops, the time complexity is linear, $O(N)$, because each element is processed by each pointer at most once.

In our next lesson, we will focus on applying this variable-size window pattern to solve a variety of longest-substring problems with different constraints. This will help you solidify your ability to recognize when to use this pattern and how to adapt the window_state and validity conditions for different problem requirements.