Sliding Window Aggregates

Welcome to the second module of our course! In the previous module, we built a strong foundation in array and subarray manipulation, culminating in techniques like Kadane's algorithm for maximum sum subarrays and the two-pointer method for in-place partitioning. Today, we begin our exploration of another powerful and highly efficient pattern: the sliding window.

This lesson will introduce you to the first variant of this pattern. Your learning outcome is to implement a fixed-size sliding window to compute aggregates over contiguous subarrays. This technique is essential for solving a class of problems where you need to analyze a continuous block of elements of a specific length, such as finding the best-performing period in stock data or identifying the densest region in a data stream. We will focus on the core logic, its implementation, and how it dramatically improves efficiency.

The Problem: Redundant Calculations

Let's begin with a classic problem that exemplifies the need for a better approach: Given an array of integers and a number k, find the maximum sum of any contiguous subarray of size k.

For example, if arr = [2, 1, 5, 1, 3, 2] and k = 3, the subarrays of size 3 are:

• [2, 1, 5] -> sum = 8
• [1, 5, 1] -> sum = 7
• [5, 1, 3] -> sum = 9
• [1, 3, 2] -> sum = 6

The maximum sum is 9.

A straightforward, brute-force solution would be to generate every possible subarray of size k, calculate its sum, and keep track of the maximum sum found.

This brute-force method has a time complexity of $O(N\times k)$ because for each of the approximately $N$ possible starting positions, we perform $k$ additions. When N and k are large, this becomes very inefficient. The core issue is redundant work. When we slide our focus from [2, 1, 5] to [1, 5, 1], we recalculate the sum of 1 and 5, even though we just computed it. The sliding window technique is designed to eliminate this very inefficiency.

The Insight: Slide, Don't Recalculate

The key insight of the sliding window pattern is to maintain a "window" of k elements and, as we slide it across the array, update our calculation in constant time, $O(1)$, for each step.

Instead of recalculating the sum of the entire new window, we can get the new sum by:

1. Subtracting the element that is sliding out of the window (the leftmost element).
2. Adding the element that is sliding into the window (the new rightmost element).

This simple update maintains the sum of the current window of k elements as we move it one position at a time. The following video explains this crucial optimization.

This process is visualized perfectly in the image below. We calculate the sum of the first window [5, 3, 4] which is 12. To get the sum of the next window, we don't re-sum 3, 4, 6. Instead, we take the previous sum (12), subtract the outgoing element (5), and add the incoming element (6).

currSum = 12 - 5 + 6 = 13

By doing this, we reduce the work at each step from $k$ additions to just one subtraction and one addition. Since we do this for all $N-k+1$ possible windows, the total time complexity becomes $O(N)$.

Implementation and a General Template

Now that you grasp the concept, let's translate it into code. We'll examine a closely related problem, LeetCode 643: "Maximum Average Subarray I". The goal is to find the maximum average of a subarray of size k. This is equivalent to finding the maximum sum and then dividing by k, so the core logic is identical.

The structure of this solution can be generalized into a template that you can adapt for any fixed-size sliding window problem. The main components are:

• A start pointer for the beginning of the window.
• An end pointer that expands the window.
• A variable (state) to hold the aggregate value of the current window (e.g., current_sum).
• A variable to track the overall best result found so far (e.g., max_sum).

A common pitfall during implementation is an off-by-one error, especially in defining loop boundaries. You must ensure your window correctly processes the entire array, including the very last possible window.

To avoid this, a common pattern is to loop from i = k to n-1, where n is the array length. In each iteration, arr[i] is the new element entering the window, and arr[i-k] is the element leaving it. This simplifies pointer management.

Connection to Prefix Sums

You might recall the Prefix Sum technique from our first module. This is another way to solve the maximum sum problem. We could pre-compute a prefix sum array in $O(N)$ time and $O(N)$ space. Then, the sum of any subarray [i, j] can be found in $O(1)$ time. We could iterate through all windows and find their sums this way.

While both Prefix Sum and Sliding Window have $O(N)$ time complexity for this problem, the sliding window approach is superior in terms of space complexity. It uses only a few variables to track the state, giving it an $O(1)$ space complexity, which is often a critical advantage.

Conclusion

In this lesson, you've learned the fundamentals of the fixed-size sliding window technique. We started by identifying the inefficiency of the brute-force approach and then introduced the core insight of the sliding window: updating the window's aggregate value in constant time.

Key Takeaways:

• The sliding window pattern is highly effective for problems involving contiguous subarrays or substrings.
• The fixed-size variant is used when the problem specifies the exact length of the window (k).
• The key optimization comes from subtracting the outgoing element and adding the incoming element, which updates the window's state in $O(1)$ time.
• This technique reduces the time complexity for many problems from $O(N\times k)$ to a much more efficient $O(N)$, typically with $O(1)$ space.

You now have a solid template for tackling fixed-window problems. In our next lesson, we will build on this foundation to explore the variable-size sliding window. This more dynamic version involves expanding and shrinking the window to find subarrays that satisfy a condition, without a predetermined size.