🪟 Sliding Window
Efficiently process sequential data by maintaining a window that slides over the array. Master fixed and variable-size window patterns.
Overview
What is Sliding Window?
Key Sliding Window Algorithms
Max Sum Subarray (Fixed)
Find max sum of k consecutive elements
Longest Substring K Distinct
Longest substring with ≤K distinct characters
Minimum Window Substring
Smallest substring containing all target characters
Longest Repeating Replacement
Longest substring with same char after k replacements
Max Consecutive Ones III
Longest 1s after flipping at most k zeros
Interactive Visualizer
Window Animation
Max Sum Subarray (Fixed) Visualizer
Watch the window slide across the array, expanding and contracting as needed.
Deep Dive: Max Sum Subarray (Fixed)
Time Complexity
Time: O(n)Space Complexity
Space: O(1)Window Type
FixedPattern Explanation
python
def maxSumSubarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sumInitialize Window
Set left=0, right=0, and any tracking variables.
Expand Window
Move right pointer, adding element to window and updating state.
Shrink (if needed)
For variable windows, move left pointer to maintain constraints.
Update Answer
Record max/min/valid window after each valid state.
Real-World Applications
Network Traffic
Monitor packet rates over time windows
Real-time Analytics
Moving averages, trend detection in streaming data
Bioinformatics
Find GC-rich regions in DNA sequences
Stock Market
Maximum profit with sliding window prices
Image Processing
Sliding window for convolution and feature detection
Natural Language
N-gram extraction, text summarization
Interview Questions
When should you use sliding window?
When the problem involves contiguous subarrays/substrings and asks for min/max/longest/shortest. Key sign: 'subarray' or 'substring' with a constraint.
What is the difference between fixed and variable window?
Fixed window has predetermined size k; just slide and update. Variable window expands/shrinks dynamically based on constraints; uses while loop to shrink when constraint is violated.
How do you identify if sliding window is applicable?
Look for: 1) Contiguous sequence, 2) Constraint (sum, distinct chars, target), 3) Need maximum/minimum window. If elements can be reordered, sliding window doesn't apply.
Knowledge Check
1. What is the key idea of sliding window?
2. What is the time complexity of sliding window?
3. Fixed-size vs variable-size window: which uses while loop to shrink?
4. What does 'k' represent in Max Sum Subarray (Fixed)?
5. When is sliding window not applicable?