Sliding Window for Optimal Subarrays

The Essence of the Sliding Window

Imagine you have a long sequence of data, like an array or a string. A brute-force approach to finding the best subarray might involve examining every single possible subarray. For an array of size $n$, this could mean looking at $O(n^2)$ subarrays, leading to slow algorithms.

The sliding window technique offers a much smarter way. It maintains a "window" — a contiguous block of elements — and slides this window across the data structure. The key insight is that as the window slides one position over, you don't need to re-calculate everything. You simply update your metrics by incorporating the new element that enters the window and removing the one that leaves.

This simple update step is what makes the technique so efficient. Because each element is processed only twice (once when it enters the window and once when it leaves), the overall time complexity is typically reduced to $O(n)$.

To understand this core idea, let's first get a high-level overview.

The fundamental mechanism of the sliding window is based on two pointers, typically left and right, which define the boundaries of the current window. The window is manipulated through three basic operations: expanding, shrinking, and sliding.

There are two primary types of sliding window problems:

1. Fixed-Size Window: The size of the window, k, is predetermined. The window slides one element at a time from the beginning to the end.
2. Variable-Size Window: The window size changes dynamically. It grows by moving the right pointer and shrinks by moving the left pointer to satisfy a certain condition.

Today, we'll master the fixed-size window and get a first look at the variable-size pattern.

Application 1: Fixed-Size Window - Maximum Sum Subarray of Size k

This is a canonical problem for the sliding window pattern and directly addresses today's learning outcome.

Problem: Given an array of integers arr and a positive integer k, find the maximum sum of any contiguous subarray of size k.

A naive solution would involve a nested loop: the outer loop picks a starting index, and the inner loop sums the next k elements. This results in an $O(n\cdot k)$ time complexity. With the sliding window, we can do much better.

The video below provides an excellent walkthrough of this exact problem, comparing the brute-force method with the optimized sliding window approach.

As the video explained, the logic is as follows:

1. Initialize: Calculate the sum of the first k elements. This is your initial windowSum and your initial maxSum.
2. Slide: Iterate from the k-th element to the end of the array. In each iteration:
   • Add the new element (arr[i]) to windowSum.
   • Subtract the element that just fell out of the window (arr[i - k]).
3. Update: After each slide, compare the new windowSum with maxSum and update maxSum if the new sum is larger.

The image below perfectly captures this process.

Now, let's look at a clean Java implementation of this technique.

This approach has a time complexity of $O(n)$ because we iterate through the array only once. The space complexity is $O(1)$ as we only use a few variables to store the sum and pointers.

Application 2: A Glimpse into Variable-Size Windows

While our main goal is mastering the fixed-size window, it's essential to be aware of its more dynamic counterpart, which you will frequently encounter in interviews. In variable-size window problems, the window expands and shrinks to meet a certain condition.

A classic example is: Find the length of the smallest contiguous subarray whose sum is greater than or equal to a target value S.

Here, the window, defined by left and right pointers, operates as follows:

1. Expand: The right pointer always moves forward, adding the new element to the window's sum.
2. Shrink: As soon as the window's sum meets the condition (i.e., sum >= S), we record the window's length and then shrink the window from the left by moving the left pointer forward until the condition is no longer met. We repeat this process, always trying to find the smallest possible window that satisfies the condition.

The article we've been using has a great section on this.

We will revisit this and other advanced patterns later, but understanding this fundamental expand-and-shrink logic is a great first step.

How to Spot a Sliding Window Problem

In a high-pressure interview setting, recognizing the right pattern is half the battle. Here are some strong indicators that a problem might be a good fit for the sliding window technique:

• The problem involves a contiguous subarray or substring.
• You are asked to find a maximum, minimum, longest, or shortest subarray/substring that satisfies some property.
• Keywords like "subarray of size k," "at most k distinct characters," or "sum greater than S" are present.
• A brute-force solution seems to involve nested loops, suggesting a potential for optimization.

For a more structured thought process to use during interviews, this is a valuable resource.

Conclusion

Today, you've added another essential algorithmic pattern to your toolkit. The sliding window technique is a fundamental approach for optimizing problems that deal with contiguous segments of data, allowing you to craft elegant and efficient $O(n)$ solutions.

Here are the key takeaways from this lesson:

• The sliding window technique processes arrays or strings by maintaining a contiguous window of elements and sliding it across the data.
• Its efficiency comes from updating calculations in $O(1)$ time as the window slides, rather than re-computing from scratch. This reduces overall time complexity to $O(n)$.
• There are two main types: fixed-size (where window size k is given) and variable-size (where the window expands and shrinks to meet a condition).
• The pattern is identifiable by problem statements involving contiguous subarrays/substrings and finding an optimal (min, max, longest, etc.) segment.

In this lesson, we focused on finding optimal subarrays. But what if you needed to answer many range sum queries over an array, not just find one optimal range? For that, a different approach is more efficient. In our next lesson, we'll explore the prefix sum technique, which allows you to answer any range sum query in $O(1)$ time after an initial $O(n)$ preprocessing step.