Variable Sliding Window for Optimal Subarrays

The Core Idea: Expand and Contract

With a fixed-size window, the window's length is constant. With a variable-size window, the length changes. The algorithm follows a simple but powerful two-phase process:

1. Expand: We grow the window by moving its right boundary (the right pointer) one step at a time. This adds a new element to our window.
2. Contract: After expanding, we check if the window still satisfies the problem's condition. If it's invalid (e.g., the sum is too high, there are too many distinct characters), we must shrink the window from the left by moving the left pointer forward until the window becomes valid again.

This dynamic of expanding and contracting allows the window to "search" for the optimal subarray size.

Example 1: Finding the Minimum Length Subarray

A classic problem for this technique is finding the shortest subarray whose elements sum up to at least a target value. This is a minimization problem.

Let's dive into this with a video that walks through the problem from scratch. It explains the inefficiency of a brute-force approach and then clearly demonstrates the variable-size sliding window solution.

Deconstructing the Logic

As you saw in the video, the logic for this minimization problem follows a clear pattern:

1. Initialize left = 0, current_sum = 0, and min_length = infinity.
2. Use a for loop to iterate with the right pointer, expanding the window. In each iteration:
   • Add nums[right] to current_sum.
3. Use a while loop to check if the window is "valid" (i.e., current_sum >= target). As long as it is:
   • Update the result: This is a potential answer, so we update min_length = min(min_length, right - left + 1).
   • Contract the window: Subtract nums[left] from current_sum.
   • Move the left pointer forward: left += 1.
4. After the loops, return min_length.

The key insight for minimization problems is that as soon as you find a valid window, you immediately try to make it smaller from the left to see if you can find an even better (shorter) solution. You update your answer inside the contraction loop.

Example 2: Finding the Maximum Length Subarray

Now let's look at a maximization problem: finding the longest subarray that satisfies a condition. Here, the logic is slightly different. Instead of shrinking as soon as a window is valid, we keep expanding as long as it's valid to find the longest possible window. We only shrink when the window becomes invalid.

A great example is the "Fruit Into Baskets" problem, which boils down to: "Find the length of the longest subarray with at most 2 distinct elements."

The following article walks through this problem, starting from a naive approach and building up to the efficient sliding window solution.

Deconstructing the Logic

Did you notice the subtle difference in the logic for this maximization problem?

1. Initialize left = 0, max_length = 0, and a state data structure (like a dictionary) to track the contents of the window (the fruit counts).
2. Use a for loop to iterate with the right pointer, expanding the window. In each iteration:
   • Add the new element fruits[right] to your state.
3. Use a while loop to check if the window has become invalid (i.e., len(state) > 2). As long as it is:
   • Contract the window: Remove fruits[left] from your state.
   • Move the left pointer forward: left += 1.
4. After the while loop, the window is guaranteed to be valid again. Now, you update the result: max_length = max(max_length, right - left + 1).
5. After the for loop finishes, return max_length.

For maximization problems, the answer is updated outside the contraction loop, at every step of the expansion where the window is valid.

The General Template

We can summarize these two patterns into a general template for variable-size sliding windows.

def variable_sliding_window(arr, ...):
    left = 0
    # Initialize state (e.g., current_sum, frequency map)
    state = ... 
    # Initialize result (e.g., min_length, max_length)
    result = ...

    for right in range(len(arr)):
        # 1. EXPAND the window by including arr[right]
        # update state...

        # 2. CONTRACT the window as long as it's invalid
        while condition_is_not_met(state):
            # update state by removing arr[left]
            left += 1
            # For MINIMIZATION problems, you often update the result HERE.

        # 3. UPDATE the result with the current valid window size
        # For MAXIMIZATION problems, you often update the result HERE.
        result = update_result(result, right - left + 1)
    
    return result

This template, presented in the resource "Sliding Window" from BlackFlow, is a powerful starting point for many problems. The crucial part is identifying the condition_is_not_met and deciding where to update your result.

Conclusion

You've now learned the versatile and powerful variable-size sliding window technique. This is a significant step up from the fixed-size window and is a cornerstone of many optimal solutions in competitive programming.

Key Takeaways:

• Variable-size sliding windows solve problems where the goal is to find an optimal (e.g., longest, shortest) contiguous subarray or substring.
• The core mechanic is to expand the window with a right pointer and contract it with a left pointer.
• A while loop is used to contract the window until a specific condition is met, restoring its validity.
• The choice of data structure to maintain the window's state (sum, set, dictionary) is critical and depends on the problem's constraints.
• Minimization problems often update the result inside the contraction loop, while maximization problems update it after.

Up Next:
We are now going to switch gears significantly. We've spent a lot of time on iterative solutions using pointers. In the next module, we'll dive into a completely different way of thinking about problems: recursion. We will start by understanding what recursion is, how to identify base cases and recursive steps, and how to trace the execution of a recursive function. This will open up a new set of strategies for solving complex problems.