--- # === IDENTITY === id: software/patterns/sliding-window-technique/2026 canonical_question: "How do I apply the sliding window technique?" aliases: - "sliding window algorithm" - "fixed size sliding window pattern" - "variable size sliding window pattern" - "shrink expand window technique" entity_type: software_reference domain: software > patterns > sliding window technique region: global jurisdiction: global temporal_scope: 2024-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Input must be a sequential data structure (array, string, linked list with indexed access) — sliding window does not apply to trees or graphs" - "For variable-size windows, the expand/shrink condition must be monotonic — if adding an element violates the condition, all larger windows containing it also violate it" - "Window boundaries (left, right) must only move forward — never decrement the right pointer or reset left to 0 mid-iteration" - "Hash map or counter state must be updated incrementally on both expand and shrink — recalculating from scratch defeats the O(n) guarantee" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need to find pairs in sorted array (e.g., two-sum on sorted input)" use_instead: "software/patterns/two-pointer-technique/2026" - condition: "Need to search for a target in sorted data" use_instead: "software/patterns/binary-search-variations/2026" - condition: "Need optimal substructure with overlapping subproblems (e.g., longest increasing subsequence)" use_instead: "software/patterns/dynamic-programming/2026" # === AGENT HINTS === inputs_needed: - key: window_type question: "Is the window size fixed or variable?" type: choice options: ["fixed_size", "variable_size"] - key: optimization question: "What are you optimizing for?" type: choice options: ["maximum", "minimum", "count", "existence"] - key: data_type question: "Are you working with a string or a numeric array?" type: choice options: ["string", "numeric_array", "mixed"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/sliding-window-technique/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/two-pointer-technique/2026" label: "Two-Pointer Technique" - id: "software/patterns/binary-search-variations/2026" label: "Binary Search Variations" - id: "software/patterns/dynamic-programming/2026" label: "Dynamic Programming Patterns" solves: [] alternative_to: [] often_confused_with: - id: "software/patterns/two-pointer-technique/2026" label: "Two-Pointer Technique (converging pointers on sorted data, not contiguous windows)" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Window Sliding Technique" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/window-sliding-technique/ type: community_resource published: 2024-12-15 reliability: high - id: src2 title: "Sliding Window Technique: A Comprehensive Guide" author: LeetCode Community url: https://leetcode.com/discuss/post/3722472/sliding-window-technique-a-comprehensive-ix2k/ type: community_resource published: 2024-06-10 reliability: high - id: src3 title: "Sliding Window Algorithm Code Template" author: labuladong url: https://labuladong.online/en/algo/essential-technique/sliding-window-framework/ type: technical_blog published: 2024-09-01 reliability: high - id: src4 title: "Sliding Window Algorithm: Complete Guide With Templates" author: LeetCopilot url: https://leetcopilot.dev/leetcode-pattern/sliding-window/guide type: technical_blog published: 2025-01-15 reliability: moderate_high - id: src5 title: "Mastering the Sliding Window Technique: A Comprehensive Guide" author: AlgoCademy url: https://algocademy.com/blog/mastering-the-sliding-window-technique-a-comprehensive-guide/ type: technical_blog published: 2025-03-20 reliability: moderate_high - id: src6 title: "Sliding Window Algorithm Explained" author: Built In url: https://builtin.com/data-science/sliding-window-algorithm type: technical_blog published: 2024-11-05 reliability: moderate_high - id: src7 title: "Coding Patterns: Sliding Window" author: emre.me url: https://emre.me/coding-patterns/sliding-window/ type: technical_blog published: 2024-08-12 reliability: moderate_high --- # Sliding Window Technique ## TL;DR - **Bottom line**: The sliding window technique processes contiguous subarrays/substrings in O(n) by maintaining two pointers (left, right) that define a window and moving them forward — never backward — while updating state incrementally. - **Key tool**: `left`/`right` pointers with expand/shrink logic — expand `right` to grow the window, shrink `left` when the window violates the constraint. - **Watch out for**: Using nested loops (O(n^2)) for problems that have a contiguous-subarray structure — sliding window reduces this to O(n). - **Works with**: Any language. Arrays, strings, and any indexed sequential data. No library dependencies. ## Constraints - Input must be sequential (array/string) — sliding window does not apply to trees or graphs - The expand/shrink condition must be monotonic for variable-size windows — if adding an element breaks validity, all larger windows containing it also break it - Window pointers must only move forward — never reset left to 0 or decrement right mid-iteration - State (sum, count, hash map) must be updated incrementally — recalculating from scratch defeats O(n) ## Quick Reference | Pattern | Window Type | Time | Space | Classic Problems | |---|---|---|---|---| | Fixed-size sum/avg | Fixed | O(n) | O(1) | Max sum subarray of size k, moving average | | Fixed-size with hash | Fixed | O(n) | O(k) | Permutation in string, anagram check | | Variable shrink (find minimum) | Variable | O(n) | O(k) | Minimum window substring, smallest subarray with sum >= target | | Variable expand (find maximum) | Variable | O(n) | O(k) | Longest substring without repeating chars, longest substring with at most k distinct | | Sliding window maximum/minimum | Fixed | O(n) | O(k) | Sliding window maximum (deque-based) | | Count-based | Variable | O(n) | O(k) | Subarrays with k different integers, count of nice subarrays | | Flip/toggle | Variable | O(n) | O(1) | Max consecutive ones III (flip at most k zeros) | | Two-frequency | Variable | O(n) | O(1) | Longest repeating character replacement | ## Decision Tree ``` START ├── Is the problem about a contiguous subarray or substring? │ ├── NO → Not a sliding window problem. Consider two pointers, DP, or binary search. │ └── YES ↓ ├── Is the window size given (fixed k)? │ ├── YES → Use FIXED-SIZE window template │ │ ├── Need max/min of window elements? → Use monotonic deque (O(n)) │ │ └── Need sum/count/frequency? → Use running sum + hash map │ └── NO → Variable-size window ↓ ├── Are you looking for the SMALLEST valid window? │ ├── YES → Use VARIABLE SHRINK template │ │ └── Expand right until valid, then shrink left to find minimum │ └── NO ↓ ├── Are you looking for the LONGEST valid window? │ ├── YES → Use VARIABLE EXPAND template │ │ └── Expand right, shrink left only when invalid, track max length │ └── NO ↓ └── Counting valid subarrays? └── YES → Use "at most K" trick: count(exactly K) = count(at most K) - count(at most K-1) ``` ## Step-by-Step Guide ### 1. Identify the window type Determine whether the problem specifies a fixed window size k or requires you to find an optimal (minimum/maximum) window. If the problem says "subarray of size k" or "every k consecutive elements," use the fixed template. If it says "smallest subarray such that..." or "longest substring where...," use the variable template. [src1] ### 2. Initialize the window state Set up your tracking variables: `left = 0`, running sum/counter/hash map, and result variable (max_sum, min_length, etc.). For hash map problems, use `collections.Counter` (Python), `Map` (JavaScript), or `HashMap` (Java). [src3] ```python left = 0 window_state = {} # or: current_sum = 0 result = float('inf') # for minimum; use float('-inf') or 0 for maximum ``` ### 3. Expand the window (move right pointer) Iterate `right` from 0 to len(arr)-1. On each step, add `arr[right]` to the window state. For sum problems, `current_sum += arr[right]`. For frequency problems, `window_state[arr[right]] += 1`. [src2] ### 4. Shrink the window (move left pointer) when constraint violated For fixed windows: shrink when `right - left + 1 > k`. For variable windows: shrink while the window is invalid (shrink template) or while the window violates the constraint (expand template). On each shrink, remove `arr[left]` from state and increment `left`. [src3] ### 5. Update the result After adjusting the window, check if the current window is a candidate for the answer. For minimum problems, update when the window becomes valid. For maximum problems, update on every step (the window is always valid or you just shrunk it to validity). [src4] **Verify**: Run through a small example manually — the left pointer should never exceed right, and both should reach the end of the array exactly once, confirming O(n). ## Code Examples ### Python: Maximum Sum Subarray of Size k (Fixed Window) ```python # Input: arr = [2, 1, 5, 1, 3, 2], k = 3 # Output: 9 (subarray [5, 1, 3]) def max_sum_subarray(arr, k): n = len(arr) if n < k: return -1 window_sum = sum(arr[:k]) # first window max_sum = window_sum for right in range(k, n): window_sum += arr[right] - arr[right - k] # slide: add new, remove old max_sum = max(max_sum, window_sum) return max_sum ``` ### Python: Minimum Window Substring (Variable Shrink) ```python # Input: s = "ADOBECODEBANC", t = "ABC" # Output: "BANC" from collections import Counter def min_window(s, t): need = Counter(t) missing = len(t) # chars still needed left = 0 best = (0, float('inf')) # (start, end) for right, char in enumerate(s): if need[char] > 0: missing -= 1 need[char] -= 1 while missing == 0: # window is valid — try to shrink if right - left < best[1] - best[0]: best = (left, right) need[s[left]] += 1 if need[s[left]] > 0: missing += 1 left += 1 return "" if best[1] == float('inf') else s[best[0]:best[1] + 1] ``` ### JavaScript: Longest Substring Without Repeating Characters (Variable Expand) ```javascript // Input: s = "abcabcbb" // Output: 3 (substring "abc") function lengthOfLongestSubstring(s) { const seen = new Map(); // char -> last index let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { if (seen.has(s[right]) && seen.get(s[right]) >= left) { left = seen.get(s[right]) + 1; // shrink past duplicate } seen.set(s[right], right); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } ``` ### Java: Max Consecutive Ones III (Variable Expand with Flip Budget) ```java // Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 // Output: 6 (flip two 0s to get [1,1,1,0,0,1,1,1,1,1,1]) public int longestOnes(int[] nums, int k) { int left = 0, zeros = 0, maxLen = 0; for (int right = 0; right < nums.length; right++) { if (nums[right] == 0) zeros++; while (zeros > k) { // too many flips — shrink if (nums[left] == 0) zeros--; left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } ``` ## Anti-Patterns ### Wrong: Using nested loops for contiguous subarray problems ```python # BAD — O(n^2) brute force for max sum subarray of size k def max_sum_brute(arr, k): max_sum = 0 for i in range(len(arr) - k + 1): current = sum(arr[i:i+k]) # recalculates entire window each time max_sum = max(max_sum, current) return max_sum ``` ### Correct: Slide the window incrementally ```python # GOOD — O(n) sliding window def max_sum_slide(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] # O(1) update max_sum = max(max_sum, window_sum) return max_sum ``` ### Wrong: Not shrinking the window correctly (forgetting to update state) ```python # BAD — shrinks left pointer but forgets to remove element from hash map def longest_unique_bad(s): seen = set() left = 0 max_len = 0 for right in range(len(s)): seen.add(s[right]) while s[right] in seen and len(seen) > right - left + 1: left += 1 # moves left but never removes s[left] from seen! max_len = max(max_len, right - left + 1) return max_len ``` ### Correct: Remove outgoing element from state on every shrink ```python # GOOD — properly maintains the set def longest_unique_good(s): seen = set() left = 0 max_len = 0 for right in range(len(s)): while s[right] in seen: seen.remove(s[left]) # remove before moving left left += 1 seen.add(s[right]) max_len = max(max_len, right - left + 1) return max_len ``` ### Wrong: Resetting left pointer to 0 on each mismatch ```python # BAD — resets left to 0, destroying O(n) guarantee def min_subarray_bad(arr, target): for right in range(len(arr)): left = 0 # WRONG: restarts from beginning every time while left <= right and sum(arr[left:right+1]) >= target: left += 1 # This is O(n^2) despite looking like sliding window ``` ### Correct: Left pointer only moves forward ```python # GOOD — left only advances, never resets def min_subarray_good(arr, target): left = 0 current_sum = 0 min_len = float('inf') for right in range(len(arr)): current_sum += arr[right] while current_sum >= target: min_len = min(min_len, right - left + 1) current_sum -= arr[left] left += 1 # only moves forward return min_len if min_len != float('inf') else 0 ``` ## Common Pitfalls - **Off-by-one in window size**: Window size is `right - left + 1`, not `right - left`. Using the wrong formula gives windows of size k-1. Fix: always use `right - left + 1` for inclusive bounds. [src1] - **Forgetting to handle empty input**: If `len(arr) < k` or `len(s) == 0`, the function should return 0 or -1 immediately. Fix: add a guard clause at the start. [src5] - **Using `while` vs `if` for shrinking**: For "find minimum" problems, use `while` (shrink as much as possible). For "find maximum" problems, `if` often suffices (shrink only when invalid). Mixing them up gives wrong results. Fix: use `while` for shrink-to-minimum, `while` for shrink-when-invalid. [src3] - **HashMap values going negative**: When tracking character frequencies, decrementing below 0 is fine (it means the window has surplus). But when checking "all characters matched," only count transitions from 1 to 0, not from -2 to -3. Fix: track a separate `matched` counter. [src2] - **Not handling duplicate characters in string windows**: When the window shrinks past a character that appears multiple times, only mark it as "missing" when its count goes above 0 (from the required count), not on every removal. Fix: check `need[char] > 0` after incrementing. [src3] - **Assuming sliding window works on non-monotonic conditions**: If adding an element can both improve and worsen the condition (e.g., array with negative numbers and you want exact sum), sliding window alone does not work. Fix: use prefix sums + hash map, or sort-based two pointers. [src4] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Finding max/min/count of contiguous subarray or substring | Elements are not contiguous (e.g., subsequence problems) | Dynamic programming | | Problem says "subarray of size k" or "window of length k" | Need to find pairs in sorted array (two-sum variant) | Two-pointer (converging) | | Optimizing longest/shortest subarray meeting a condition | Array contains negative numbers and you need exact subarray sum | Prefix sum + hash map | | Condition is monotonic (expanding only makes it worse/better) | Problem requires comparing non-adjacent elements | Binary search or divide & conquer | | String pattern matching within a window (anagrams, permutations) | Need to find longest increasing subsequence (non-contiguous) | Patience sorting / DP | | Counting subarrays satisfying a property | Data structure is a tree or graph | BFS/DFS traversal | ## Important Caveats - Sliding window is a specialization of the two-pointer technique — every sliding window uses two pointers, but not every two-pointer problem is a sliding window (converging pointers on sorted arrays are two-pointer, not sliding window) - For "count subarrays with exactly K distinct elements," you cannot directly use sliding window — use the identity `exactly(K) = atMost(K) - atMost(K-1)` with two sliding window passes - The O(n) time complexity assumes O(1) state updates; if your state update involves sorting or scanning the entire window, the total complexity may be O(n log k) or O(nk) — use a monotonic deque or balanced BST to maintain O(n) or O(n log k) for min/max queries within a window - When elements can be negative, the monotonic property breaks for sum-based problems — `current_sum >= target` does not imply `current_sum + next >= target`, so the shrink step may skip valid windows ## Related Units - [Two-Pointer Technique](/software/patterns/two-pointer-technique/2026) - [Binary Search Variations](/software/patterns/binary-search-variations/2026) - [Dynamic Programming Patterns](/software/patterns/dynamic-programming/2026)