Variable Sliding Window
Overview
While a fixed window has a strict size, a Variable Sliding Window expands and shrinks dynamically to meet a specific condition (e.g., 'Find the longest substring without repeating characters' or 'Smallest subarray with a sum >= target'). You expand the window by moving a `right` pointer, and if the window becomes 'invalid', you shrink it by moving a `left` pointer until it becomes valid again. It is a masterpiece for optimizing string/array problems.
Syntax
The `right` pointer aggressively adds elements. The `left` pointer aggressively removes them to find the absolute minimum length.
public int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE;
int windowSum = 0;
int left = 0;
// Expand the window by moving the right pointer
for (int right = 0; right < nums.length; right++) {
windowSum += nums[right];
// While the window is VALID, record the length and try to SHRINK it
while (windowSum >= target) {
minLength = Math.min(minLength, right - left + 1);
// Shrink from the left
windowSum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}Common Pitfalls
- Thinking the time complexity is O(N^2) because of the nested `while` loop. The `left` pointer only traverses the array once, making it O(N).
- Calculating the window length incorrectly. The length between two inclusive pointers is `right - left + 1`.
Interview Tips
- Keywords indicating Variable Sliding Window: 'Longest/Smallest Subarray/Substring', 'At most K distinct', 'Sum >= S'.
Real-World Example
TCP packet congestion control algorithms use variable sliding windows to maximize data transmission speeds, dynamically expanding the packet window when the network is fast, and shrinking it when packets are dropped.
// The window size (number of packets sent) fluctuates based on network reliability
public void congestionControl(boolean packetDropped) {
if (!packetDropped) {
windowSize *= 2; // Expand aggressively
} else {
windowSize /= 2; // Shrink to prevent network crash
}
}