Sliding Window Technique on Arrays

1. From Brute Force to an Efficient "Window"

Imagine you're asked to find the maximum sum of any contiguous subarray of size 3 in a given array. The naive, or brute-force, approach would involve two nested loops. The outer loop picks a starting point, and the inner loop iterates through the next 3 elements to calculate their sum. You'd repeat this for every possible starting point.

While this works, its time complexity is $O(n\cdot k)$, where $n$ is the array size and $k$ is the subarray size. For a large array, this is inefficient. This is where the sliding window technique provides a significant optimization, reducing the complexity to a clean $O(n)$.

The core idea is to maintain a "window" of a certain size that "slides" over the array. Instead of recalculating the sum of the entire window every time it moves, we perform a simple and efficient update: subtract the element that leaves the window from the left and add the element that enters from the right.

This video from the TAP ACADEMY YouTube channel provides an excellent introduction, first by explaining the problem and then by showing the inefficient brute-force solution.

Now that you've seen the slow way, let's look at the elegant, efficient alternative.

2. The Fixed-Size Sliding Window

The most straightforward application of this technique is with a fixed-size window. Let's tackle the same problem: Find the maximum sum of a contiguous subarray of size k.

The algorithm is as follows:

1. Initialize: Calculate the sum of the first k elements. This is your initial windowSum and your current maxSum.
2. Slide: Start a loop from the k-th element to the end of the array. In each iteration:
   a. Add the current element (the one entering the window from the right) to windowSum.
   b. Subtract the element that is falling off the left side of thewindow. This element will be at index i - k.
   c. Compare the new windowSum with maxSum and update maxSum if it's larger.
3. Return: After the loop, maxSum holds the result.

The same video you just watched provides a fantastic explanation and implementation of this exact logic.

This pattern is your go-to solution for any problem that asks for an optimal value (max, min, etc.) over a contiguous subarray of a fixed length. The article "Sliding Window Technique in Java" from dev.to offers a concise code template for this.

3. The Variable-Size Sliding Window

Things get more interesting when the window size isn't fixed. In these scenarios, the window grows and shrinks dynamically based on a certain condition. A classic example is: Find the minimum length of a contiguous subarray whose sum is greater than or equal to a target value S.

Here, we don't know the size of the subarray beforehand. The logic adjusts:

1. Expand the Window: Use a right pointer to iterate through the array, adding each element to a windowSum. This expands the window to the right.
2. Check and Shrink: As soon as windowSum meets the condition (i.e., windowSum >= S), we have a potential answer.
   a. Record its length (right - left + 1) and update our minLength if this one is smaller.
   b. Now, try to find an even smaller valid window by shrinking it from the left: subtract the leftmost element from windowSum and increment the left pointer.
   c. Keep shrinking as long as the condition windowSum >= S remains true.
3. Continue: Once the condition is violated, the inner shrinking loop stops, and the outer loop continues expanding the window to the right.

This "expand-and-shrink" dynamic is the essence of the variable-size window. The article from Labuladong provides a robust mental framework for this pattern.

Now, let's see this variable-size pattern in action with a video walkthrough.

4. How to Spot the Pattern in an Interview

Recognizing when to apply an algorithm is just as important as knowing how to implement it. Here are the tell-tale signs of a sliding window problem:

• The problem involves an array or a string.
• You are asked to find properties of a contiguous subarray or substring. This is the biggest clue.
• The problem asks for a longest, shortest, minimum, or maximum value that satisfies a certain condition.
• The problem might state a fixed window size k, clearly pointing to a fixed-size window.

This video section summarizes these points perfectly.

Conclusion

Today, you've added another essential interview pattern to your toolkit. The sliding window technique is a powerful way to turn seemingly complex subarray problems with $O(n^2)$ or $O(n\cdot k)$ complexity into highly efficient $O(n)$ solutions.

Here are the key takeaways:

• Core Idea: The sliding window technique efficiently processes contiguous subarrays by avoiding redundant calculations. It updates a window's value by adding the incoming element and subtracting the outgoing one.
• Fixed-Size Window: Used when the subarray length k is given. The window slides one element at a time, and you update your answer at each step.
• Variable-Size Window: Used when the subarray length is unknown. The window expands until a condition is met, then shrinks from the left to find the optimal solution while the condition still holds.
• Problem Recognition: Look for problems on arrays/strings involving "contiguous subarrays/substrings" and optimizing for a "longest/shortest/min/max" value.

In our next lesson, we will explore another common interview pattern: solving frequency-counting problems using a HashMap. You'll see how a HashMap can be a powerful auxiliary data structure used inside a sliding window to solve even more complex problems, like finding the longest substring with no repeating characters.