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:

publicstaticintMaxSumSubarray(int[]arr,intk){intmaxSum=0,windowSum=0;for(inti=0;i<arr.Length;i++){windowSum+=arr[i];// Add the current element to the window sumif(i>=k-1)// When the window size reaches k{maxSum=Math.Max(maxSum,windowSum);// Update max sum if necessarywindowSum-=arr[i-(k-1)];// Remove the first element of the window}}returnmaxSum;}// Example Usageint[]arr={2,1,5,1,3,2};intk=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:

publicstaticintLongestUniqueSubstring(strings){HashSet<char>charSet=newHashSet<char>();intleft=0,maxLength=0;for(intright=0;right<s.Length;right++){while(charSet.Contains(s[right])){charSet.Remove(s[left]);// Remove the leftmost character to resolve repetitionleft++;// Slide the left pointer}charSet.Add(s[right]);// Add the current charactermaxLength=Math.Max(maxLength,right-left+1);// Update maxLength}returnmaxLength;}// Example Usagestrings="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:

publicstaticintSmallestSubarrayWithSum(int[]arr,inttarget){intminLength=int.MaxValue,windowSum=0,left=0;for(intright=0;right<arr.Length;right++){windowSum+=arr[right];while(windowSum>=target){minLength=Math.Min(minLength,right-left+1);// Update minLengthwindowSum-=arr[left];// Remove the leftmost elementleft++;// Slide the left pointer}}returnminLength==int.MaxValue?0:minLength;}// Example Usageint[]arr={4,2,2,7,8,1,2,8,10};inttarget=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:

publicstaticintLongestOnesWithReplacement(int[]arr,intk){intleft=0,maxLength=0,zerosCount=0;for(intright=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}returnmaxLength;}// Example Usageint[]arr={1,1,0,0,1,1,1,0,1};intk=2;Console.WriteLine(LongestOnesWithReplacement(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.