Ultimate Guide to master the Sliding Window Technique

The Sliding Window technique is a powerful and efficient method used to solve problems involving arrays, strings, and sequences. Instead of using brute force methods that may result in time complexity issues, sliding window optimizes the process by reducing redundant calculations, making it a popular approach among competitive programmers.

In this guide, we’ll break down the sliding window technique, explore its different types, walk through examples, and provide advanced insights to help you master this concept.

What is the Sliding Window Technique?

The sliding window technique refers to creating a window that slides across a given data structure (like an array or string) to perform calculations. The idea is to maintain a window of fixed or variable size and slide it across the data to minimize redundant computations.

Why Use the Sliding Window?

Many problems involve analyzing subarrays, substrings, or subsequences. Instead of recalculating values for each new subarray from scratch, sliding window allows you to update the results based on the previous window, thus improving time efficiency.

For instance, to find the maximum sum of a subarray of size k in an array, brute force would have a time complexity of O(n*k), while sliding window reduces it to O(n).

Common Applications of Sliding Window

• Maximum or minimum sum of subarrays
• Longest substring without repeating characters
• Count of substrings that meet certain conditions
• Problems involving continuous subarrays or sub-sequences

Types of Sliding Window

1.Fixed-Size Sliding Window

A fixed-size sliding window is used when the window length is predetermined. For example, if we need to find the sum of every subarray of size k, we create a window of size k and slide it across the array.

Example Problem: Maximum Sum of Subarray of Size k

Problem Statement: Given an array, find the maximum sum of subarray with length k.

Solution:

• Initialize two pointers: the start and end of the window.
• Keep track of the current sum of the window and slide it across the array.
• Update the maximum sum as the window moves forward.

2.Variable-Size Sliding Window

A variable-size sliding window is used when the window size changes dynamically based on certain conditions. This is common in problems that involve substrings or subsequences where the window expands or shrinks until certain criteria are met.

Example Problem: Longest Substring Without Repeating Characters

Problem Statement: Given a string, find the length of the longest substring without repeating characters.

Solution:

• Use two pointers to represent the current window.
• Expand the window by moving one pointer until a repeated character is encountered.
• Shrink the window by moving the second pointer to remove characters until the substring no longer contains duplicates.

How Does the Sliding Window Technique Work?

To understand how the sliding window technique works, let’s look at the steps involved in its implementation:

1. Initialize the Window

• For fixed-size windows, start by calculating the sum or value for the first window of size k.
• For variable-size windows, initialize pointers to mark the start and end of the current window.

2. Expand the Window

• Move the right pointer (or window end) to include the next element in the window.

3. Shrink the Window

• If the current window violates a condition (like containing duplicates), move the left pointer (or window start) to reduce the window size.

4. Track Results

• As the window slides, track the relevant results (e.g., maximum sum, longest substring) by updating the result based on the changes to the window.

Optimizing the Sliding Window

To further optimize the sliding window technique, you can use additional data structures like HashMaps or HashSets to track elements and reduce time complexity.

Using HashMaps

For problems like finding the longest substring with unique characters, a HashMap can store the frequency or last occurrence of characters within the window. This way, you can quickly adjust the window size based on the characters encountered.

Two-pointer Approach

Sliding window is often implemented using a two-pointer approach. The left and right pointers define the bounds of the window, and they are moved based on problem conditions.

Space-Time Complexity

Sliding window techniques typically reduce the time complexity of problems to O(n), making them much faster than brute-force methods, which are often O(n²) or worse.

Sliding Window Examples

Let’s walk through a couple of common sliding window problems.

Example 1: Maximum Sum Subarray of Size k

public class SlidingWindow {
    // Method to find the maximum sum of a subarray of size k
    public static int maxSumSubarray(int[] arr, int k) {
        // Base case: if the array length is less than k
        if (arr.length < k) {
            System.out.println("Array length is less than the size of the subarray.");
            return -1;
        }

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

        // Sliding the window over the array and updating the sum
        int windowSum = maxSum;
        for (int i = k; i < arr.length; i++) {
            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;
        System.out.println("Maximum sum of a subarray of size " + k + ": " + maxSumSubarray(arr, k));
    }
}

Explanation:

• The maxSumSubarray function takes an array arr and the window size k.
• It calculates the sum of the first subarray (the first window), then slides the window across the array, updating the sum by subtracting the first element of the previous window and adding the next element.

Output:

Maximum sum of a subarray of size 3: 9

Example 2: Longest Substring Without Repeating Characters

import java.util.HashSet;

public class SlidingWindow {
    // Method to find the length of the longest substring without repeating characters
    public static int longestUniqueSubstring(String s) {
        HashSet<Character> set = new HashSet<>();  // To track characters in the current window
        int maxLength = 0;                         // To store the maximum length
        int left = 0;                              // Left pointer for the sliding window

        for (int right = 0; right < s.length(); right++) {
            // If we find a repeating character, shrink the window
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }

            // Add the current character to the window
            set.add(s.charAt(right));

            // Update the maximum length of the substring
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Length of longest substring without repeating characters: " + longestUniqueSubstring(s));
    }
}

Explanation:

• The longestUniqueSubstring function uses a sliding window approach with a HashSet to track unique characters within the window.
• It expands the window by moving the right pointer and shrinks the window from the left when a duplicate character is encountered.

Output:

Length of longest substring without repeating characters: 3

How it Works:

• As the right pointer moves through the string, if a duplicate character is found, the left pointer is moved until the duplicate character is no longer in the window. The window is thus dynamic, shrinking and expanding as needed.

Practice Problems

To master the sliding window technique, practice is key. Here are a few problems to help you:

• Leetcode 209: Minimum Size Subarray Sum
• Leetcode 3: Longest Substring Without Repeating Characters
• Leetcode 76: Minimum Window Substring
• Leetcode 239: Sliding Window Maximum

Conclusion

The Sliding Window Technique is a versatile and efficient method for solving many array and string problems. Whether you’re working with fixed or variable-size windows, this approach can significantly reduce the time complexity of your solution. Keep practicing different problems, and soon sliding window will become a go-to technique in your coding toolkit.