Sliding Window Pattern

Let's begin with the Sliding Window pattern, a commonly used technique to solve problems involving subarrays or substrings.

Sliding Window Pattern

Concept:

The sliding window technique is used to solve problems that involve subarrays (or substrings) of a fixed or variable size within a larger array or string. Instead of recalculating values repeatedly, the window "slides" over the input, updating the result as it goes. This improves efficiency compared to brute force methods.

Example Problem:

Find the maximum sum of k consecutive elements in an array.

Problem Statement:

Given an array of integers arr[] and an integer k, find the maximum sum of any contiguous subarray of size k.

Brute Force Approach:

In the brute force method, we would calculate the sum of each subarray of size k using nested loops. This would take O(n * k) time complexity, which is inefficient for large arrays.

Optimized Sliding Window Approach:

Using the sliding window approach, we can achieve this in O(n) time.

Java Code Implementation:

public class SlidingWindowExample {
    
    // Method to find the maximum sum of k consecutive elements
    public static int findMaxSum(int[] arr, int k) {
        // Edge case check
        if (arr.length < k) {
            System.out.println("Invalid input: array size is less than k");
            return -1;
        }

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

        // Current sum is initialized to maxSum
        int currentSum = maxSum;

        // Slide the window from index 1 to (n-k)
        for (int i = k; i < arr.length; i++) {
            currentSum += arr[i] - arr[i - k];  // Add the next element and remove the previous one
            maxSum = Math.max(maxSum, currentSum);  // Update maxSum if current sum is greater
        }

        return maxSum;
    }

    // Main method to test the sliding window implementation
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
        int k = 3;  // Window size
        System.out.println("Maximum sum of " + k + " consecutive elements: " + findMaxSum(arr, k));
    }
}

Explanation:

1. We first compute the sum of the first k elements.
2. Then, we slide the window across the array. For each slide, we add the next element and subtract the element that is left out of the window.
3. At each step, we update the maximum sum.

Expected Output:

For the input array {1, 3, 2, 6, -1, 4, 1, 8, 2} and k = 3, the output will be:

Maximum sum of 3 consecutive elements: 13

Time Complexity:

The time complexity is O(n), where n is the number of elements in the array. This is because we calculate the sum for the first k elements once and then slide the window in a single pass through the array.

Space Complexity:

The space complexity is O(1) as we are only using a constant amount of extra space for variables like maxSum and currentSum.

Big O Notation Explanation:

• O(n) means that the time it takes to run the algorithm grows linearly with the size of the input. In our example, we only go through the array once (n elements), making it efficient.
• O(1) space complexity indicates that we aren't using any additional space that grows with the input size.

This is the basic sliding window pattern. As we progress, we can explore more advanced problems that use variations of this approach.

View All Patterns Here