Implementing Sliding Window Aggregates

Hello! In our last lesson, we saw how two pointers moving in the same direction could efficiently compact an array in-place. We used a "read" pointer and a "write" pointer to partition the array based on a simple condition.

Today, we'll continue exploring patterns with pointers moving in the same direction, but for a completely different class of problems. We will introduce the Sliding Window technique. This lesson focuses on the first variant: the fixed-size sliding window. You'll learn how to maintain a window of a constant size as it slides over an array and efficiently calculate an aggregate value, like a sum or average, within that window. This is a foundational pattern for solving many problems involving contiguous subarrays or substrings.

The Sliding Window Concept

Imagine you have a long sequence of data, and you want to analyze a "chunk" of it at a time. For example, finding the highest 7-day average temperature from a year's worth of daily readings. You wouldn't recalculate the average from scratch for every possible 7-day period. Instead, as you move from one day to the next, you'd simply subtract the reading from 8 days ago and add today's reading.

This is the essence of the sliding window pattern. It's a conceptual window that slides over a portion of data, typically an array or string.

A Canonical Problem: Maximum Sum Subarray of Size K

Let's ground this with a classic interview problem:

Given an array of integers nums and a number k, find the maximum sum of a contiguous subarray of size k.

For example, if nums = [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.

The Brute-Force Approach

The most straightforward way to solve this is to generate every possible subarray of size k, calculate its sum, and keep track of the maximum sum found. This involves a nested loop structure: the outer loop sets the starting point of the subarray, and the inner loop sums up k elements. This results in a time complexity of $O(n\cdot k)$, where n is the length of the array.

This approach works, but it's inefficient because it performs many redundant calculations. When we slide our window from [2, 1, 5] to [1, 5, 1], we recalculate the sum of 1 and 5, even though we just computed it.

To get a clear picture of this inefficiency, the following video explains the brute-force method and why it leads to a quadratic runtime.

The Optimized Sliding Window Solution

We can avoid redundant work by using a rolling aggregate. Instead of re-computing the entire sum for each new window, we can update the sum from the previous window in constant time, $O(1)$.

The process is as follows:

1. Initialize: Calculate the sum of the very first window of k elements. This will be our initial currentSum and maxSum.
2. Slide and Update: Iterate from the k-th element to the end of the array. In each step, "slide" the window one position to the right by:
   • Adding the new element that just entered the window.
   • Subtracting the old element that just left the window.
3. Track Maximum: After each slide, compare the currentSum with maxSum and update maxSum if the new sum is greater.

This simple optimization reduces the overall time complexity to $O(n)$, as we only need to iterate through the array once. The space complexity is $O(1)$ since we only need a few variables to store the current and maximum sums.

The image below demonstrates this process step-by-step for k=3. Notice how Window Sum is updated efficiently at each step.

To solidify your understanding of the logic, the following reading from AlgoCademy provides a concise, step-by-step breakdown.

Implementation in JavaScript

Now let's translate this logic into code. The implementation involves a single loop. A key detail is correctly identifying the element to subtract, which is at index i - k.

The AlgoCademy article you just looked at provides a clean JavaScript implementation. Let's study it.

For a more detailed, line-by-line walkthrough of a similar implementation, the next segment of the video from The Code Creative is excellent. The presenter clearly explains how the indices work, which can be a common point of confusion.

Generalizing the Pattern

The power of this pattern is that it's not limited to calculating sums. You can use a fixed-size sliding window to maintain any kind of "rolling aggregate." The core logic of adding a new element's contribution and removing an old one's remains the same.

For instance, you could solve:

• Maximum average of a subarray of size k: The logic is identical. Just divide the maxSum by k at the end.
• Maximum number of vowels in a substring of length k: Instead of adding numbers, you'd check if the entering/leaving characters are vowels and increment/decrement a vowelCount.

The following short video clip highlights how this same pattern applies to these different problems.

Recognizing that a problem can be solved with a fixed-size sliding window is a key skill. Clues often include phrases like "subarray/substring of size k," "contiguous," and the need to find a max, min, or average.

Conclusion

In this lesson, you've learned the fixed-size sliding window pattern, a powerful tool for efficiently processing contiguous blocks of data.

Key Takeaways:

• Problem Type: This pattern is ideal for problems involving contiguous subarrays or substrings of a fixed length k.
• Core Idea: Instead of re-computing from scratch, you maintain a "rolling aggregate" (like a sum or count) by updating it in $O(1)$ time as the window slides.
• Efficiency: This technique transforms an inefficient $O(n\cdot k)$ brute-force solution into a much faster $O(n)$ linear-time solution.
• Implementation: The logic involves initializing the window, then looping once more through the array to slide, update the aggregate, and track the desired result.

We've focused on windows of a fixed size. But what if the size of the "valid" window can change? In our next lesson, we will explore the variable-size sliding window pattern, where you'll learn to dynamically expand and shrink the window to find the longest or shortest subarray that satisfies a certain condition.