All about Sliding Window Pattern software design technique

The sliding window pattern is a technique commonly used in software design to solve problems that involve a contiguous subset of elements in a data structure, usually arrays or lists. This approach is efficient for problems where you need to consider all contiguous subarrays or subsequences of a given size.

This method is popular because it reduces the time complexity of certain problems by avoiding redundant calculations, allowing the solution to be achieved in linear time (O(n)) instead of quadratic time (O(n²)).

Concept:

The sliding window pattern involves creating a window that slides over the data structure to examine a subset of elements. As the window moves from the start to the end of the data structure, the subset of elements within the window changes. This technique is particularly useful when the problem requires repeated computation over overlapping sections of the data.

Here’s a simple anecdote to help a kid understand the sliding window pattern:

The Cookie Jar Adventure

Once upon a time, in a small village, there was a little girl named Aashi. Aashi loved cookies, and his mom baked a big batch of cookies every weekend. She put all the cookies in a large jar and placed it on the kitchen counter.

One Saturday morning, Aashi’s mom gave him a fun challenge. She said, “Aashi, if you can find the best three cookies in a row from this jar, you can have them as a special treat!” Aashi was excited but puzzled. How could she figure out which set of three cookies in a row was the best?

Here’s what Aashi did:

1. Start with the First Three Cookies: Aashi looked at the first three cookies in the jar and added up their deliciousness points. Let’s say the first three cookies had points 2, 3, and 4. So, the total was 2 + 3 + 4 = 9.

2. Slide to the Next Three Cookies: Aashi then moved his attention to the next set of three cookies. She removed the point of the first cookie from his total and added the point of the next cookie in line. If the next cookie had 5 points, the new total was 9–2 + 5 = 12.

3. Keep Sliding and Adding: Aashi continued this process, always removing the point of the cookie she left behind and adding the point of the new cookie. This way, she didn’t have to start counting from the beginning every time. She just updated his total quickly.

4. Find the Highest Total: As she slid her attention over each set of three cookies, she kept track of the highest total she found. Eventually, she found the set of three best cookies.

That’s the sliding window pattern in action — simple and sweet!

Common Use Cases

1. Finding Maximum or Minimum in Subarrays: Determine the maximum or minimum values in every subarray of a fixed size.
2. Sum of Subarrays: Calculate the sum of all subarrays of a given length.
3. Substring Problems: Solve problems involving substrings of a string, such as finding the longest substring without repeating characters.
4. Median of Subarrays: Compute the median of each subarray of a given length.

A simple Java code example that demonstrates the sliding window pattern using the scenario of finding the maximum sum of any subarray of size k in a given array:

public class SlidingWindowExample {
    public static int maxSumSubarray(int[] arr, int k) {
        int n = arr.length;
        if (n < k) {
            throw new IllegalArgumentException("Array length must be greater than or equal to k");
        }

        // Compute the sum of the first window
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        int maxSum = windowSum;

        // Slide the window from start to end of the array
        for (int i = 0; i < n - k; i++) {
            // Update the window sum by subtracting the element that is leaving the window
            // and adding the element that is entering the window
            windowSum = windowSum - arr[i] + arr[i + k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        int result = maxSumSubarray(arr, k);
        System.out.println("The maximum sum of any subarray of size " + k + " is: " + result);
    }
}