Sliding Window for Subarrays and Substrings

What is a Sliding Window?

At its heart, the sliding window technique is an optimization. It's designed for problems where you need to find something in a contiguous block of data, like a subarray or a substring.

Imagine you have a long array and you need to find the subarray of a specific size, say k=3, that has the largest sum.

The brute-force way would be:

1. Look at the first three elements, calculate their sum.
2. Look at elements 2 through 4, calculate their sum.
3. Look at elements 3 through 5, calculate their sum.
4. ...and so on, keeping track of the biggest sum you find.

This works, but it's inefficient. For each window, you're re-summing elements you've already summed before. The sliding window technique eliminates this redundant work.

To see this inefficiency and the clever solution, watch the first couple of minutes of the following video.

As the video explained, instead of re-calculating the sum for each new window, you can simply "slide" the window forward by one position.

When you slide the window, you just need to:

1. Subtract the element that is no longer in the window (the one on the far left).
2. Add the new element that has just entered the window (the one on the far right).

This way, you perform only two operations per step, regardless of how large the window is. This simple idea is what reduces the complexity from $O(N\cdot K)$ to a much faster $O(N)$.

A Step-by-Step Example: Maximum Subarray Sum

Let's trace this logic with a concrete example.
Problem: Given arr = [1, 2, 6, 2, 4, 1] and k = 3, find the maximum sum of any contiguous subarray of size 3.

Step 1: Initialize the Window

• Calculate the sum of the first window (k=3 elements): 1 + 2 + 6 = 9.
• Our current_sum is 9.
• Our max_sum so far is also 9.

Step 2: Slide the Window to the Right

• The window moves to cover [2, 6, 2].
• To get the new sum, we take the current_sum (9), subtract the element leaving (1), and add the element entering (2).
• new_sum = 9 - 1 + 2 = 10.
• Our current_sum is now 10.
• We update max_sum because 10 is greater than 9. max_sum is now 10.

Step 3: Slide Again

• The window moves to cover [6, 2, 4].
• new_sum = 10 - 2 + 4 = 12.
• current_sum is now 12.
• We update max_sum because 12 is greater than 10. max_sum is now 12.

Step 4: Slide to the End

• The window moves to cover [2, 4, 1].
• new_sum = 12 - 6 + 1 = 7.
• current_sum is now 7.
• max_sum remains 12, since 7 is smaller.

We've reached the end of the array. The maximum sum we found is 12.

From Logic to Code: A LeetCode Problem

Now let's see how to implement this in Python by solving a classic LeetCode problem. The problem is "Maximum Average Subarray I," which is a slight variation of what we just did—instead of the max sum, we want the max average. The core logic remains identical.

Code Implementation Summary

Here is a Python function that implements the logic for the maximum sum problem, based on the principles from the video.

def max_sum_subarray(nums, k):
    # 1. Handle edge case
    if len(nums) < k:
        return 0

    # 2. Calculate the sum of the first window
    current_sum = sum(nums[:k])
    max_sum = current_sum

    # 3. Slide the window from the k-th element to the end
    for i in range(k, len(nums)):
        # Subtract the element leaving the window and add the element entering
        current_sum = current_sum - nums[i - k] + nums[i]
        
        # Update the maximum sum found so far
        max_sum = max(max_sum, current_sum)
        
    return max_sum

# Example usage:
arr = [1, 2, 6, 2, 4, 1]
k = 3
print(f"The maximum sum is: {max_sum_subarray(arr, k)}")  # Output: The maximum sum is: 12

This code snippet is an optimized version from the article "Competitive Programming #1: Sliding Window Technique" on Medium.

• Time Complexity: $O(N)$. We iterate through the array once to build the initial sum (or we can do it in the main loop), and then one more time to slide the window. Each element is added to and subtracted from the sum exactly once.
• Space Complexity: $O(1)$. We only use a few variables to store the current sum, max sum, and loop indices, regardless of the input array's size.

Conclusion

Today you've mastered the fixed-size sliding window, a fundamental technique for your competitive programming toolkit. It's a simple yet powerful idea that can dramatically speed up your solutions for problems on contiguous subarrays and substrings.

Key Takeaways:

• Fixed-size sliding window is an optimization technique for problems on contiguous data blocks of a constant size k.
• It avoids redundant calculations by efficiently updating a running value (like a sum or count) as the window moves.
• The core mechanic is to subtract the outgoing element and add the incoming element at each step.
• This approach reduces the time complexity from a brute-force $O(N\cdot K)$ to an optimal $O(N)$.

Up Next:
The real power of sliding windows comes when the window size isn't fixed. In our next lesson, we will explore the variable-size sliding window technique. You'll learn how to expand and shrink a window dynamically to find subarrays or substrings that satisfy a condition, such as finding the shortest subarray whose sum is at least a certain value.