Demystifying Algorithms: Sliding Window

What is the Sliding Window Technique?

The Sliding Window technique is a method used to optimize solutions for problems involving contiguous subarrays or substrings. It "slides" a window of a fixed size or dynamically adjusted size across the data to reduce redundant computations. This technique is highly efficient for problems that involve sums, products, or conditions within a subset of elements in a sequence.

The Technical View

• Time Complexity: (O(n)) (in most cases).
  • The window typically traverses the input array once, resulting in linear time complexity.
• Space Complexity: (O(1)).
  • Often, only a few variables are needed to maintain the current state of the window.

An Anorak's Compendium

The Sliding Window technique uses two pointers (or indices) to represent the start and end of the current window. As the window slides across the data, it dynamically adjusts its size or properties based on the problem constraints, enabling the efficient reuse of previous computations.

A Fifth-Grader's Summary

Imagine you’re looking through a telescope that can only see part of the sky at once. Instead of scanning the whole sky repeatedly, you move the telescope smoothly from left to right, focusing on one small section at a time.

Real-World Example

Think of finding the maximum temperature over any 3-day period in a month. Instead of calculating the sum for each 3-day window from scratch, you "slide" a window, subtracting the first day's temperature as you add the next day's, saving time and effort.

Examples with Code, Iteration Details, and Optimized Patterns

1. Maximum Sum Subarray of Size (k)

Problem: Find the maximum sum of any subarray of size (k).

Code:

public static int MaxSumSubarray(int[] arr, int k)
{
    int maxSum = 0, windowSum = 0;

    for (int i = 0; i < arr.Length; i++)
    {
        windowSum += arr[i]; // Add the current element to the window sum

        if (i >= k - 1) // When the window size reaches k
        {
            maxSum = Math.Max(maxSum, windowSum); // Update max sum if necessary
            windowSum -= arr[i - (k - 1)]; // Remove the first element of the window
        }
    }

    return maxSum;
}

// Example Usage
int[] arr = { 2, 1, 5, 1, 3, 2 };
int k = 3;
Console.WriteLine(MaxSumSubarray(arr, k)); // Output: 9

What Happens in Each Iteration:

1. (i = 0): Add (arr[0] = 2). (windowSum = 2).
2. (i = 1): Add (arr[1] = 1). (windowSum = 3).
3. (i = 2): Add (arr[2] = 5). (windowSum = 8).
   • Update (maxSum = 8).
   • Slide the window: Subtract (arr[0] = 2). (windowSum = 6).
4. (i = 3): Add (arr[3] = 1). (windowSum = 7).
   • (maxSum = 8).
   • Slide the window: Subtract (arr[1] = 1). (windowSum = 6).
5. (i = 4): Add (arr[4] = 3). (windowSum = 9).
   • Update (maxSum = 9).
   • Slide the window: Subtract (arr[2] = 5). (windowSum = 4).
6. (i = 5): Add (arr[5] = 2). (windowSum = 6).
   • (maxSum = 9).

Final Result: (maxSum = 9).

2. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Code:

public static int LongestUniqueSubstring(string s)
{
    HashSet<char> charSet = new HashSet<char>();
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.Length; right++)
    {
        while (charSet.Contains(s[right]))
        {
            charSet.Remove(s[left]); // Remove the leftmost character to resolve repetition
            left++; // Slide the left pointer
        }

        charSet.Add(s[right]); // Add the current character
        maxLength = Math.Max(maxLength, right - left + 1); // Update maxLength
    }

    return maxLength;
}

// Example Usage
string s = "abcabcbb";
Console.WriteLine(LongestUniqueSubstring(s)); // Output: 3

What Happens in Each Iteration:

1. (right = 0): Add 'a'. (charSet = {a}), (maxLength = 1).
2. (right = 1): Add 'b'. (charSet = {a, b}), (maxLength = 2).
3. (right = 2): Add 'c'. (charSet = {a, b, c}), (maxLength = 3).
4. (right = 3): 'a' already in set. Remove 'a'. Add 'a'.
   • (charSet = {b, c, a}), (maxLength = 3).
5. (right = 4): 'b' already in set. Remove 'b'. Add 'b'.
   • (charSet = {c, a, b}), (maxLength = 3).

Final Result: (maxLength = 3).

3. Smallest Subarray with a Sum Greater Than Target

Problem: Find the length of the smallest subarray with a sum greater than or equal to a target.

Code:

public static int SmallestSubarrayWithSum(int[] arr, int target)
{
    int minLength = int.MaxValue, windowSum = 0, left = 0;

    for (int right = 0; right < arr.Length; right++)
    {
        windowSum += arr[right];

        while (windowSum >= target)
        {
            minLength = Math.Min(minLength, right - left + 1); // Update minLength
            windowSum -= arr[left]; // Remove the leftmost element
            left++; // Slide the left pointer
        }
    }

    return minLength == int.MaxValue ? 0 : minLength;
}

// Example Usage
int[] arr = { 4, 2, 2, 7, 8, 1, 2, 8, 10 };
int target = 15;
Console.WriteLine(SmallestSubarrayWithSum(arr, target)); // Output: 2

What Happens in Each Iteration:

1. (right = 0): Add (arr[0] = 4). (windowSum = 4).
2. (right = 1): Add (arr[1] = 2). (windowSum = 6).
3. (right = 2): Add (arr[2] = 2). (windowSum = 8).
4. (right = 3): Add (arr[3] = 7). (windowSum = 15).
   • Update (minLength = 4). Subtract (arr[0] = 4). (windowSum = 11).
5. (right = 4): Add (arr[4] = 8). (windowSum = 19).
   • Update (minLength = 2). Subtract (arr[1] = 2). (windowSum = 17).

Final Result: (minLength = 2).

4. Longest Subarray with Ones After Replacement

Problem: Find the longest subarray containing only ones after replacing up to (k) zeros.

Code:

public static int LongestOnesWithReplacement(int[] arr, int k)
{
    int left = 0, maxLength = 0, zerosCount = 0;

    for (int right = 0; right < arr.Length; right++)
    {
        if (arr[right] == 0)
        {
            zerosCount++; // Increment the zero count
        }

        while (zerosCount > k)
        {
            if (arr[left] == 0)
            {
                zerosCount--; // Decrement the zero count
            }
            left++; // Slide the left pointer
        }

        maxLength = Math.Max(maxLength, right - left + 1); // Update maxLength
    }

    return maxLength;
}

// Example Usage
int[] arr = { 1, 1, 0, 0, 1, 1, 1, 0, 1 };
int k = 2;
Console.WriteLine(LongestOnesWith

Replacement(arr, k)); // Output: 6

What Happens in Each Iteration:

1. (right = 0): Add 1. (maxLength = 1).
2. (right = 1): Add 1. (maxLength = 2).
3. (right = 2): Add 0. (zerosCount = 1), (maxLength = 3).
4. (right = 3): Add 0. (zerosCount = 2), (maxLength = 4).
5. (right = 6): Add 1. (zerosCount = 2), (maxLength = 6).

Final Result: (maxLength = 6).

Conclusion

The Sliding Window technique is a cornerstone of efficient algorithms. By dynamically managing a window’s size, it avoids brute force approaches and ensures optimal performance. Mastering this pattern is essential for solving many algorithmic challenges.