Fixed-Size Sliding Window Technique

1. The Problem: Maximum Sum Subarray of Size K

Let's begin by clearly defining the problem. You are given an array of integers and a number k. Your task is to find the maximum sum that can be obtained from any contiguous subarray of size exactly k. A contiguous subarray is a sequence of adjacent elements.

For example, consider the array arr = [1, 7, 6, 2, 3, 4, 5] and k = 2.
The subarrays of size 2 are: [1, 7], [7, 6], [6, 2], [2, 3], [3, 4], and [4, 5].
Their sums are: 8, 13, 8, 5, 7, and 9.
The maximum among these sums is 13.

To formalize this, let's review the problem statement from GeeksforGeeks.

2. Approach 1: The Brute-Force Method

Following our established method, let's start with the most intuitive, brute-force solution. The idea is straightforward:

1. Generate every possible contiguous subarray of size k.
2. Calculate the sum of each of these subarrays.
3. Keep track of the maximum sum found so far.

To implement this, we can use two nested loops. The outer loop (i) will determine the starting index of our subarray. Since a subarray of size k cannot start past n-k (where n is the array length), this loop will run from 0 to n-k. The inner loop (j) will then iterate k times from the starting index i to sum up the elements of the current window.

The following video provides an excellent, detailed explanation of this naive approach.

Now, let's look at the implementation and complexity from your primary resource, the takeuforward article.

This brute-force solution is correct, but as you'll see in interviews, correctness is just the first step. For large arrays, an $O(N\cdot K)$ solution can be too slow. This inefficiency motivates our search for an optimal approach.

3. The Sliding Window: A More Efficient Paradigm

The inefficiency in the brute-force method comes from recalculating the sum of each window from scratch. Consider the windows [1, 7, 6] and [7, 6, 2]. They share two elements, 7 and 6. When we move from the first window to the second, we are performing redundant calculations by re-adding 7 and 6.

The sliding window technique eliminates this redundancy. Imagine a "window" of size k that slides over the array. As it slides one step to the right:

• A new element enters the window from the right.
• An old element leaves the window from the left.

To update the sum, we simply take the sum of the previous window, subtract the element that left, and add the element that entered. This is an $O(1)$ operation per slide.

This simple video from TAP ACADEMY provides a great analogy to build intuition.

4. Approach 2: The Optimal Sliding Window Solution

Now, let's formalize the sliding window algorithm for our problem:

1. Initialization: Calculate the sum of the first k elements. This is the sum of our initial window. Initialize maxSum with this value.
2. Sliding: Start a loop from the k-th index to the end of the array. In each step, this loop represents the new element entering the window.
   • Update the current window's sum by adding the new element (arr[i]) and subtracting the element that just slid out of the window's left side (arr[i-k]).
   • Compare this updated window sum with maxSum and update maxSum if the new sum is larger.
3. Result: After the loop finishes, maxSum will hold the maximum sum of any subarray of size k.

This process involves a single pass through the array, making it much more efficient. The following video walks through this entire optimal process, from the initial sum calculation to the sliding logic and the final Java implementation.

To solidify this, let's turn back to the Striver/TUF article, which is our main guide. It presents the same logic in a concise format.

By applying the sliding window pattern, we transformed an $O(N\cdot K)$ algorithm into a linear time $O(N)$ solution, which is the kind of optimization interviewers look for.

Conclusion

In this lesson, we introduced the powerful sliding window technique by applying it to a concrete problem. This pattern is fundamental for efficiently solving problems involving contiguous subarrays or substrings.

Key Takeaways:

• Problem: Find the maximum sum of a contiguous subarray of a fixed size k.
• Brute-Force Solution: Use nested loops to check every possible subarray of size k. This results in an $O(N\cdot K)$ time complexity.
• Sliding Window Insight: Instead of recalculating sums, we can maintain a "window" of size k and slide it across the array. The sum is updated in $O(1)$ time at each step by subtracting the leaving element and adding the entering one.
• Optimal Solution: This leads to an elegant single-pass algorithm with $O(N)$ time complexity and $O(1)$ space complexity.

You've now mastered the fixed-size sliding window. In our next lesson, we will build on this foundation to tackle problems where the window size is not fixed. We'll explore variable-size sliding windows to solve problems like finding the "longest substring without repeating characters."