Sliding Window Technique for Arrays

1. From Brute Force to an Efficient "Window"

Imagine you're asked to find the maximum sum of any three consecutive elements in an array. The brute-force way would be to calculate the sum of arr[0], arr[1], arr[2], then arr[1], arr[2], arr[3], and so on. Notice the repetitive calculations? The sum of arr[1] and arr[2] is computed in both steps.

The sliding window technique eliminates this redundancy. Instead of recalculating the sum for each new window, we simply "slide" the window one step to the right by:

1. Adding the new element that enters the window.
2. Subtracting the old element that leaves the window.

This single pass approach is what gives the sliding window its linear time efficiency.

To get a solid conceptual overview, let's watch a video that explains what this technique is, why it's so much better than brute-force, and how to start recognizing problems where it can be applied.

As the video explained, sliding window problems generally fall into two categories, which we'll explore next.

2. Type 1: Fixed-Size Sliding Window

This is the most straightforward variant, used when the problem specifies a fixed window size, k.

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

The Logic

1. Calculate the sum of the first k elements. This is our initial windowSum and our initial maxSum.
2. Iterate from the k-th element to the end of the array.
3. In each step, "slide" the window:
   • Add the current element to windowSum.
   • Subtract the element that just fell out of the window's left side (i.e., arr[i-k]).
4. Update maxSum with the new windowSum if it's larger.

Java Implementation

Let's look at a concise implementation of this logic. The key is the line windowSum += arr[i] - arr[i - k], which performs the slide in a single, efficient operation.

Here is the code from the article for your reference:

public int maxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
 
    // Sum of the first k elements (initial window)
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
 
    int maxSum = windowSum;
 
    // Slide the window from k to the end of the array
    for (int i = k; i < arr.length; i++) {
        // Add the new element and remove the old one
        windowSum += arr[i] - arr[i - k]; 
        maxSum = Math.max(maxSum, windowSum);
    }
 
    return maxSum;
}

3. Type 2: Variable-Size Sliding Window

This variant is more dynamic and powerful. The window expands and shrinks based on a condition. It doesn't have a fixed size k. Instead, you're usually looking for the longest or shortest subarray that satisfies a property.

Problem: Given an array of positive integers arr and a target integer S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S.

The Logic

We use two pointers, left and right, to define the window's boundaries.

1. Initialize left = 0, windowSum = 0, and minLength = infinity.
2. Expand the window by moving the right pointer forward, adding arr[right] to windowSum.
3. Once windowSum >= S, we have a potential answer!
   • Record its length (right - left + 1).
   • Now, try to get a better (smaller) answer. Shrink the window from the left by subtracting arr[left] from windowSum and incrementing left.
   • Keep shrinking as long as windowSum is still >= S.
4. Repeat until right reaches the end of the array.

Java Implementation

This pattern typically involves a for loop for the right pointer (to expand) and a nested while loop for the left pointer (to shrink).

The code demonstrates this expand-and-shrink logic perfectly:

public int smallestSubarrayWithSum(int[] arr, int target) {
    int left = 0, windowSum = 0, minLength = Integer.MAX_VALUE;

    for (int right = 0; right < arr.length; right++) {
        // Expand the window to the right
        windowSum += arr[right];

        // While the condition is satisfied, shrink the window from the left
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= arr[left];
            left++;
        }
    }

    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

4. Sliding Windows with Auxiliary Data Structures

For more complex problems, you might need to track more than just a sum. A common scenario involves tracking the frequency of elements or the number of unique elements within the window. This is where you can combine the sliding window pattern with a HashMap or a HashSet.

Problem: Given a string s and an integer k, find the length of the longest substring with at most k distinct characters.

The logic is similar to the variable-size window, but our condition for shrinking is based on the size of a HashMap that stores character frequencies.

This pattern is extremely common in interviews for problems involving strings and character counts.

5. How to Spot Sliding Window Problems

Since your goal is to excel in technical interviews, recognizing when to apply a pattern is as important as knowing how to implement it.

Key Heuristics:

• Input: The problem involves an array or string.
• Contiguous: It asks for a subarray or substring (implying elements are next to each other).
• Optimization: It asks for a min, max, longest, shortest, or count of something.
• Brute-Force Hint: Your initial thought involves nested loops, which would be O(n^2) or worse.

Conclusion

You've now added another essential algorithmic pattern to your arsenal. The sliding window technique is a powerful optimization that elegantly solves a wide range of problems involving contiguous data. By understanding its fixed and variable-size forms, you are well-equipped to tackle many common questions in competitive programming and technical interviews.

Key Takeaways:

• The Sliding Window Technique optimizes problems on contiguous subarrays/substrings from a brute-force O(n^2) to an efficient O(n).
• Fixed-Size Windows are used when the subarray length k is given. The window is updated by adding the new element and subtracting the old one.
• Variable-Size Windows are used to find the longest/shortest subarray that meets a condition. They expand from the right and shrink from the left when the condition is met (or violated).
• Auxiliary data structures like a HashMap can be used within the window to track complex states, such as character frequencies.

Preview of the next lesson:
In our next lesson, we will step back from algorithmic patterns slightly to cover a practical and essential topic for any Java programmer in a competitive context: using Java's built-in sorting methods like Arrays.sort() and Collections.sort(). We'll discuss how they work under the hood (their time complexity) and when to use them for maximum efficiency.