Sliding Window Optimization

Welcome back! In our previous lesson, we explored the fixed-size sliding window, where we maintained an aggregate over a contiguous block of data of a constant size k. This was efficient because we could update the aggregate in $O(1)$ time by adding the new element and subtracting the one that just left the window.

Today, we move on to a more dynamic and flexible version of this pattern: the variable-size sliding window. As the name suggests, the window's size is no longer fixed. Instead, it will expand and contract based on conditions we define. This lesson's goal is to learn how to manage this dynamic window, particularly for problems where expanding and shrinking the window have predictable, monotonic effects—for example, where making the window bigger always increases a sum, and making it smaller always decreases it. This property is the key to solving a whole new class of problems efficiently.

From a Fixed Pane to an Accordion

Think of the fixed-size window as a rigid frame you slide across your data. A variable-size window is more like an accordion: you can stretch it out by including more elements or compress it by removing elements from the start.

This dynamic is controlled by two pointers, left and right, which both start at the beginning of the array. The right pointer moves forward to expand the window, while the left pointer moves forward only when needed to shrink it.

This technique is powerful when the property we're tracking behaves monotonically. For instance, if we're working with an array of positive numbers:

• Expanding the window by adding a new element will always increase the sum.
• Shrinking the window by removing an element from the left will always decrease the sum.

This predictability allows us to systematically "search" for a subarray that meets our criteria without checking every single possibility.

A Canonical Problem: Smallest Subarray with a Given Sum

Let's ground this with a classic problem that perfectly demonstrates the pattern:

Given an array of positive integers nums and a target integer S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S. If there is no such subarray, return 0.

For example, if nums = [2, 1, 5, 2, 3, 2] and S = 7:

• [2, 1, 5] has a sum of 8 (length 3).
• [5, 2] has a sum of 7 (length 2).
• The smallest length is 2.

The brute-force approach would be to check every possible subarray, which would be $O(n^2)$ — too slow for large inputs. We can do much better.

The following video introduces this exact problem and briefly touches on the brute-force approach, which helps motivate the need for a more optimized solution.

The Variable-Window Solution

Here’s the strategy using a variable-size window:

1. Initialize: Set up left = 0, windowSum = 0, and minLength = Infinity.
2. Expand: Iterate through the array with the right pointer. In each step, add nums[right] to windowSum.
3. Check and Shrink: As soon as windowSum >= S, we have a valid (though maybe not the smallest) window. Now, we try to make it as small as possible by shrinking it from the left:
   • Record its length: minLength = min(minLength, right - left + 1).
   • Subtract nums[left] from windowSum.
   • Increment left.
   • Repeat this shrinking process as long as windowSum remains >= S.

Once the while loop finishes (meaning windowSum < S), we continue our main for loop, moving right to expand the window again.

To see this logic in motion, the next video provides an excellent visualization.

Now that you have the visual intuition, let's examine a clean implementation of this logic. The following resource provides both a brute-force and the optimized sliding window solution in JavaScript.

Generalizing the Pattern: Minimum vs. Maximum Problems

The problem we just solved is a "find the minimum" type of problem. We expand until a condition is met, then shrink as much as possible while the condition remains met.

There's a related but slightly different structure for "find the maximum" problems (e.g., "longest substring with at most K distinct characters"). For these, the logic is flipped:

1. Expand the window.
2. If the condition is violated, shrink the window from the left until it becomes valid again.
3. Update the maximum length found so far with the current valid window.

The following article provides excellent templates for both scenarios, which is key to turning this concept into a reusable problem-solving tool.

To see the "find maximum" pattern in action, let's look at the example provided in that same article.

Conclusion

In this lesson, we've unlocked the variable-size sliding window, a versatile and efficient pattern for a wide range of array and string problems.

Key Takeaways:

• Core Mechanic: The window is defined by left and right pointers. It expands by incrementing right and shrinks by incrementing left.
• Monotonicity is Key: The pattern is most effective when the condition being checked changes monotonically (predictably increases or decreases) as the window expands or shrinks.
• Two Main Variants:
  • Finding a Minimum: Expand until valid, then shrink while still valid to find the smallest possible window.
  • Finding a Maximum: Expand, and if you become invalid, shrink just enough to become valid again. The answer is the largest valid window seen.
• Time Complexity: This pattern typically achieves a linear time complexity of $O(n)$, because each element is visited by the left and right pointer at most once.

In our last example, we saw a glimpse of using a Map to track character counts. This is a very common extension of the sliding window pattern. In our next lesson, we will dive deep into this technique and learn how to maintain character frequencies and satisfaction counts inside a sliding window to solve even more complex problems.