Variable Sliding Window
Overview
The Variable Sliding Window is a more complex evolution of the fixed window. Instead of the window size being locked to 'K', the window size dynamically expands and shrinks based on a specific condition.
The logic operates like a caterpillar:
1. The right pointer (head) moves forward, expanding the window and adding data until the window violates a condition.
2. Once the condition is violated, the left pointer (tail) moves forward, shrinking the window and removing data until the condition is satisfied again.
This pattern is used when you are asked to find the Longest or Shortest contiguous subarray that meets a target condition (e.g., 'Find the longest substring without repeating characters' or 'Find the smallest subarray whose sum is >= Target').
Syntax
public class VariableSlidingWindow {
// Problem: Find length of the smallest contiguous subarray whose sum is >= target
public static int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE;
int currentSum = 0;
int left = 0; // Tail of the caterpillar
// right is the head of the caterpillar
for (int right = 0; right < nums.length; right++) {
// Expand the window to the right
currentSum += nums[right];
// While the condition is met, try to shrink it from the left
// to find the SMALLEST possible window!
while (currentSum >= target) {
// Record the valid window size
minLength = Math.min(minLength, right - left + 1);
// Shrink the window: subtract the left element and move tail forward
currentSum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}Common Pitfalls
- Using an
ifstatement instead of awhileloop for shrinking. When the window becomes invalid, shrinking the left side by just 1 step might not be enough to make it valid again. You must always use awhile(condition)loop to continuously shrink the left side until validity is restored. - Calculating window length incorrectly. The formula for the number of elements in a window bounded by
leftandrightindices is ALWAYSright - left + 1. Forgetting the+ 1is a guaranteed bug. - Applying this pattern to arrays with negative numbers (for sum problems). If the problem involves finding a target sum and the array contains negative numbers, expanding the window doesn't guarantee the sum increases, destroying the caterpillar logic. You must use Prefix Sums + HashMaps instead.
Interview Questions
while loop nested inside a for loop?Because both the left and right pointers only ever move forward. The right pointer iterates over the array once. The left pointer iterates over the array at most once. Therefore, each element is processed a maximum of twice (added once, removed once). 2N operations is O(N) time complexity.
Use a Variable Sliding Window with a HashSet. The right pointer adds characters to the set. If it hits a character already in the set, the condition is violated. The left pointer must then continuously remove characters from the set and shrink the window until that duplicate character is ejected.
Real-World Example
Data Compression Algorithms (like LZ77 used in ZIP and PNG files) use dynamic sliding windows. The algorithm scans a file and looks backwards in a sliding window to find the longest exact match of the data it is currently looking at. If it finds a match, it replaces the current data with a short pointer to the previous occurrence, compressing the file.
// Conceptual LZ77 Window Match
int windowSize = findLongestMatchInWindow(data, currentPosition, slidingWindow);
if (windowSize > 3) {
writeCompressionPointer(windowSize);
currentPosition += windowSize; // Skip ahead
} else {
writeLiteralByte(data[currentPosition]);
currentPosition++;
}Check Your Knowledge
Test your understanding of Variable Sliding Window with these quick questions.