Algorithmic Patterns: The Ultimate Guide to Sliding Window

The Sliding Window pattern is one of the most vital algorithmic techniques for optimizing array and string problems. Instead of repeatedly processing overlapping subarrays - which leads to brute-force quadratic O(N^2) or O(N*K) complexities, the sliding window technique reuses previous computations to achieve linear time complexity $O(N)$. In this guide, we will break down the mechanics, core variations, identification rules, real-world applications, and a curated list of 18 LeetCode problems with key solution strategies. 💡 What is the Sliding Window Pattern? A sliding window performs operations over a contiguous sub-segment (subarray or substring) of data structure. As the window "slides" across the array from left to right, elements entering and leaving the window are updated incrementally. Time Complexity Comparison Brute-Force Nested Loops: O(N^2) or O(N * K) Sliding Window Strategy: O(N) (each element is processed at most twice: once entering and once leaving) 🛠️ Recognition & Identification Rules When to Use Sliding Window Contiguous Input: The problem requires evaluating contiguous subarrays or substrings. Window Metric Criteria: You need to calculate statistics such as minimum/maximum length, sum, average, or character frequency targets. Monotonicity Property: Expanding the window strictly increases (or maintains) a target metric, while shrinking the window strictly decreases it (e.g., sum > K or at most K distinct elements over positive numbers). When NOT to Use Sliding Window Negative Numbers in Sum Constraints: If an array contains negative numbers and you are tracking a cumulative sum, expanding the window does not monotonically increase the sum. Use Prefix Sum + HashMap instead. Non-Contiguous Sequences: If the problem asks for subsequences (where elements do not need to be adjacent), sliding window fails. Non-Monotonic Metrics: If moving pointers does not give a predictable increase or decrease in your decision metric. 🔄 Fixed vs. Variable Length Sliding Window Sliding window algorithms fall into two primary structural variants: Feature Fixed-Length Window Variable-Length Window Window Boundary Fixed size $K$ Expands and contracts dynamically based on conditions Pointer Movement left and right advance together right expands continuously; left contracts when condition breaks Core Goal Calculate a target metric (sum, max, avg, frequency match) across all subarrays of exact length $K$ Find the longest, shortest, or total count of valid subarrays matching a criterion State Operations Add element at right, drop element at left Add element at right; loop-shrink from left while invalid (or valid) 📊 Visualizing Window Mechanics 1. Fixed-Length Sliding Window In a fixed window, both pointers maintain a constant distance $K$. flowchart LR subgraph Iteration 1 A1["[ A B C ] D E"] end subgraph Iteration 2 A2["A [ B C D ] E"] end subgraph Iteration 3 A3["A B [ C D E ]"] end Iteration 1 -->|Slide Right: Add D, Remove A| Iteration 2 Iteration 2 -->|Slide Right: Add E, Remove B| Iteration 3 2. Variable-Length Sliding Window In a variable window, right expands the window until a condition is broken, prompting left to shrink the window back into a valid state. flowchart TD Start([Start Array Traversal]) --> Expand[Add arr[right] to Window] Expand --> Check{Is Window Valid?} Check -- Yes --> UpdateAns[Update Best Result Max/Min Length] UpdateAns --> IncrementRight[right++] Check -- No --> Shrink[Remove arr[left] from Window] Shrink --> IncrementLeft[left++] IncrementLeft --> Check IncrementRight --> LoopEnd{End of Array?} LoopEnd -- No --> Expand LoopEnd -- Yes --> End([Return Result]) 🌐 Real-World Applications Financial Systems: Calculating moving averages of real-time stock prices over $N$-day windows. Network Engineering: API Rate Limiting (e.g., Sliding Window Log/Counter algorithms to restrict requests per second). Audio/Video Processing: Processing live audio streaming chunks of continuous audio buffers. 💻 Code Blueprints Fixed-Length Template (Java/Python Concept) def fixed_sliding_window(arr, k): window_sum = sum(arr[:k]) max_sum = window_sum for right in range(k, len(arr)): window_sum += arr[right] - arr[right - k] # Add incoming, subtract outgoing max_sum = max(max_sum, window_sum) return max_sum Variable-Length Template def variable_sliding_window(arr, condition_target): left = 0 window_state = 0 best_res = 0 for right in range(len(arr)): # 1. Include right element window_state += arr[right] # 2. Shrink window while invalid while not is_valid(window_state, condition_target): window_state -= arr[left] left += 1 # 3. Update result best_res = max(best_res, right - left + 1) return best_res 🏋️ Problem Playbook & Key Strategies Category A: Fixed-Length Window Problems 1. Maximum Average Subarray I (LeetCode 643) Strategy: Maintain a window sum of length k. Slide across the array by adding nums[right] and subtracting nums[right - k]. Finally, return max_sum / k. 2. Minimum Recolors to Get K Consecutive Black Blocks (LeetCode 2379) Strategy: Use a fixed window of size k. Count the number of white blocks ('W') inside the current window. Track the minimum white block count across all windows. 3. Subarrays Size K with Average Greater than or Equal to Threshold (LeetCode 1343) Strategy: Transform the target average to target sum: target_sum = (threshold * k). Maintain a running sum of window size k and increment the count whenever window_sum >= target_sum. 4. Grumpy Bookstore Owner (LeetCode 1052) Strategy: Calculate baseline satisfied customers without using technique. Then, run a fixed window of length minutes to maximize the extra unsatisfied customers converted to satisfied. Add maximum extra gain to baseline. 5. Contains Duplicate II (LeetCode 219) Strategy: Use a dynamic HashSet acting as a sliding window of max size $k$. For each element, check if it exists in the set. If yes, return true. If window size exceeds $k$, remove nums[i - k] from the set. 6. Defuse the Bomb (LeetCode 1658) Strategy: Circular array windowing. Determine window bounds depending on whether k > 0 or k < 0. Slide a fixed window of length |k| across the array using modulo index mapping: index % N. Category B: Dynamic Variable-Length Window Problems 7. Longest Substring Without Repeating Characters (LeetCode 3) Strategy: Maintain a lastIndexSeen HashMap. When a duplicate character is encountered at right, jump left = max(left, lastIndexSeen[char] + 1) to keep the window unique. 8. Max Consecutive Ones III (LeetCode 1004) Strategy: Maintain a zero counter within the window. Whenever zero count exceeds k, shrink from left until zero count is less than k. Record max window length (right - left + 1). 9. Fruit Into Baskets (LeetCode 904) Strategy: Equivalent to "Longest Subarray with at most 2 Distinct Elements". Use a frequency map. Shrink from left when map.size() > 2. 10. Minimum Size Subarray Sum (LeetCode 209) Strategy: Expand right to increase running sum. Once sum >= target, contract left in a inner while loop to find the minimum dynamic window length while updating answer. 11. Subarray Product Less Than K (LeetCode 713) Strategy: Expand right and multiply into current_product. If current_product >= k, divide out nums[left]. The number of valid subarrays ending at right is (right - left + 1). 12. Longest Repeating Character Replacement (LeetCode 424) Strategy: Track the maximum frequency of any single character in the current window (maxFreq). The window is valid if (windowLength - maxFreq)