You're in a coding interview. The problem mentions a **contiguous subarray** or **substring**, some constraint, and "longest", "shortest", "maximum", or "minimum". You suspect it's a **sliding window pattern** question… but you’re not 100% sure: - Should this be a fixed-size sliding window or a variable-size one? - Where do you put the **expand** and **shrink** logic? - How do you keep the **window invariant** correct without off-by-one bugs? This guide is the **pillar article** for everything sliding window: - What the **sliding window algorithm** really is (beyond “two pointers”) - How to instantly recognize sliding window LeetCode problems - Universal **sliding window template** patterns in Python, Java, and JavaScript - Deep-dive sliding window examples (with diagrams and debugging notes) - Advanced variations: at-most-`k`, deques, 2D, and more - A senior-level **sliding window debugging** checklist If you internalize this, the sliding window pattern stops being a gimmick and becomes a reliable **O(N) window technique** you can deploy in almost any interview, especially on **sliding window LeetCode** problems. --- ## What Is the Sliding Window Pattern? At a high level, the **sliding window pattern** is a way to process all **contiguous subarrays or substrings** of a sequence in linear time by reusing work between neighboring windows. Instead of recomputing from scratch for every candidate range, you: - Maintain a **window** `[left, right]` over the data - **Expand** the window by moving `right` (include new elements) - **Shrink** the window by moving `left` (remove old elements) - Maintain some **window state** (sum, frequency map / counter, max, etc.) Think of it as a moving interval: ```text Index: 0 1 2 3 4 5 Array: [7, 2, 5, 8, 1, 3] Window 1: [0,2] → [7,2,5] Window 2: [1,3] → [2,5,8] Window 3: [2,4] → [5,8,1] ``` Instead of recomputing the sum for each window, we: - Add the new element entering from the right - Subtract the element leaving from the left ### Real-world analogy Imagine scanning a log file with a **moving magnifying glass**: - The magnifying glass shows **one interval** at a time - As you slide it, one line exits on the left, one enters on the right - You track some metric inside the glass: error count, max latency, etc. Sliding window is the code version of that magnifying glass. ### Why sliding window works Sliding window works when: - The problem is about a **contiguous** region (subarray/substring) - You can update the **window state** in **O(1)** or amortized **O(1)** when you: - Add an element (`expand`) - Remove an element (`shrink`) - There is a clear notion of **window validity** (the window either satisfies or violates some condition) Under these conditions, both pointers together move at most `N` steps each. That gives you an **O(N)** pass instead of an **O(N²)** brute-force search. ### Why interviews love this pattern Sliding window LeetCode questions test: - Your ability to recognize **problem structure** (contiguous + constraint) - Your understanding of **stateful algorithms** (maps, counters, deques) - Your discipline around **boundary conditions** and **off-by-one** behavior It’s also a great discriminator: many candidates know “two pointers”, but far fewer can articulate **why the window invariant is correct** and debug it under pressure. --- ## Core Intuition: How Sliding Window Actually “Thinks” At an intuitive level, the sliding window algorithm does three things: 1. **Explore** by expanding the window to the right 2. **Repair** by shrinking from the left when the window becomes invalid 3. **Optimize** by tracking the best valid window (max/min length, sum, etc.) ### Window as a moving interval We always track an interval: ```text 0 1 2 3 4 5 a b c a b b ↑ ↑ left right window = s[left:right+1] ``` The code invariant is simple: - At any time, the window is the substring or subarray between `left` and `right` **inclusive** - Window size is always `right - left + 1` (this is where most off-by-one errors come from) ### Expand → shrink → update Mentally, every variable-size sliding window follows this cycle: 1. **Expand**: move `right` and update the window state (sum, counts, etc.) 2. **Shrink**: while the window violates your condition, move `left` and undo the state 3. **Update**: now that the window is valid again, update your answer ```python left = 0 for right in range(len(arr)): add(arr[right]) # expand while not is_valid(): # shrink until invariant restored remove(arr[left]) left += 1 update_answer(left, right) # window [left, right] is valid here ``` ### Window invariant The **window invariant** is the condition you maintain after the shrink loop finishes. Examples: - “Window contains **at most k distinct** characters” - “Window sum is **≤ target**” - “Window contains **all characters of T** in required frequencies” The invariant rule is: > After the shrink loop, the window must always be **valid**. This is the heart of the sliding window algorithm: - Expand may temporarily break validity - Shrink repairs it - Once repaired, you know `[left, right]` is the “best” window ending at `right` that satisfies your rules ### Memory and state transitions Sliding window is powerful because state changes are **local**: - When you **expand**, you only touch the new element at `right` - When you **shrink**, you only touch the old element at `left` Typical window state structures: - **Scalar**: sum, count of zeros, count of 1s - **Frequency map / counter**: counts per character/number - **Set**: presence/absence of elements (e.g., no duplicates) - **Deque**: monotonic queue for max/min in window The art is choosing the simplest state that lets you test **window validity** in O(1). --- ## How to Identify Sliding Window Problems Instantly You don’t want to recognize sliding window halfway through a brute-force attempt. Here’s a **checklist** and language cues to spot them immediately. ### Quick checklist Use sliding window if: - You are working over a **single array or string** - The problem asks about a **contiguous subarray/substring** - You need to **optimize** some metric: - Longest/shortest window - Maximum/minimum sum, average, or count - Number of windows satisfying a constraint - You can maintain the state with **incremental updates** If any of these are false, step back and consider other patterns (two pointers, prefix sums, DP). ### Phrases in problem statements Strong sliding window signals: - “contiguous subarray” or “substring” - “longest / shortest” - “at most k”, “at least k” - “no more than k”, “no less than k” - “maximum number of … in any window of size k” Examples: - “Find the **length of the longest substring** without repeating characters” - “Find the **minimum length subarray** with sum ≥ target” - “Given a binary array, return the **maximum number of consecutive 1s** if you can flip at most k zeros” ### Deciding: fixed-size vs variable-size sliding window Ask: 1. **Is window size fixed?** - Text: “window of size k”, “subarray of length k” - Use a **fixed-size sliding window** (no shrink loop; left just trails right by `k`). 2. **Is window size flexible?** - Text: “longest / shortest”, “at most k distinct”, “sum at least target” - Use a **variable-size sliding window** with the expand–shrink–update pattern. When in doubt, start with variable-size; fixed-size is just a simpler special case. ### Sliding window vs prefix sum vs DP vs two pointers If you’re unsure whether to use sliding window: - Consider **prefix sum** when: - You need **exact sum equals k** and values can be negative - Order still matters, but greedy expand/shrink logic fails See: [Sliding Window vs Prefix Sum](/leetcode-pattern/sliding-window/sliding-window-vs-prefix-sum). - Consider classic **two pointers** when: - You care about **pairs or endpoints**, not the whole range in between - Input is or can be **sorted** - Problems like 2-sum (sorted), 3-sum, container with most water See: [Sliding Window vs Two Pointers](/leetcode-pattern/sliding-window/sliding-window-vs-two-pointers). - Consider **dynamic programming** when: - You’re dealing with subsequences (non-contiguous) - The state depends on **multiple earlier positions**, not just the current window For deeper pattern-recognition pitfalls, read [Common Sliding Window Mistakes](/leetcode-pattern/sliding-window/common-sliding-window-mistakes). --- ## Types of Sliding Windows (Complete Overview) There are several flavors of the sliding window algorithm. Being explicit about which one you’re using clarifies both code and correctness. ### Fixed-size sliding window **Definition**: The window always contains exactly `k` elements. Examples: - “Max sum of any subarray of size k” - “Number of subarrays of length k with average ≥ threshold” Key traits: - No validity condition; size itself is the constraint - Left pointer increments when `right` reaches `k - 1` Sketch (sum over window of size `k`): ```python window_sum = 0 best = -float("inf") for right in range(len(nums)): window_sum += nums[right] if right >= k - 1: # window reached size k best = max(best, window_sum) window_sum -= nums[right - k + 1] # shrink from left ``` ### Variable-size sliding window **Definition**: Window grows and shrinks based on a **validity constraint**. Examples: - “Longest substring without repeating characters” - “Longest substring with at most k distinct characters” - “Minimum window substring that contains all characters of t” Key traits: - Expand until invalid, then shrink until valid - Often used to find **optimal window size** (max or min) ### Two-ended windows Sometimes both ends move in more complex ways: - One pointer sweeps, the other follows with **conditional jumps** - Example: partitioning problems where you maintain a window of “good” elements, but occasionally reset left after a hard boundary This is still sliding window as long as: - You maintain a contiguous interval - You update state only when `left` or `right` moves ### Shrink-to-fit vs grow-to-fit windows - **Shrink-to-fit**: - Expand aggressively - Shrink only when the window becomes invalid (“too big”, “too many distinct chars”) - Common for “longest” / “at most k” problems - **Grow-to-fit**: - Expand until the window first **becomes valid** - Then shrink to find the **smallest valid** window - Common for “minimum window substring” or “shortest subarray with sum ≥ target” Recognizing which one you’re using prevents subtle bugs in the shrink loop. ### Monotonic sliding windows (deques) For some problems, basic counters aren’t enough: - “Sliding window maximum” - “Sliding window minimum” You want to maintain the window’s max/min in O(1) **without scanning the entire window each time**. The trick is to use a **monotonic deque**: - Store indices in decreasing (for max) or increasing (for min) order of values - Pop from back while the new element is “better” - Pop from front if it falls out of the window This is a specialized but important variation of the sliding window algorithm. You’ll see it in harder sliding window LeetCode interview questions. ### 2D / matrix windows For 2D problems (submatrices, grids), you often: - Fix two row boundaries - **Compress** rows into a 1D array of column sums - Run a 1D sliding window or Kadane-style algorithm on that Details are in [How to Apply Sliding Window in 2D / Matrix Problems](/leetcode-pattern/sliding-window/sliding-window-2d-matrix-problems). --- ## Universal Templates (Multi-Language) For interview performance, you want **one mental sliding window template** per language, not ad-hoc loops. Below are canonical **variable-size** and **fixed-size** templates in Python, Java, and JavaScript. For more depth and annotations, see [Sliding Window Template Explained](/leetcode-pattern/sliding-window/sliding-window-template-explained). ### Python #### Variable-size sliding window template ```python def sliding_window_var(arr, condition) -> int: left = 0 result = 0 # or float("inf") for minimum problems window = {} # dict / Counter / set / scalar depending on problem for right, value in enumerate(arr): # 1. Expand: include arr[right] in window state # update_window_add(window, value) # 2. Shrink: while window is invalid, move left while not is_valid(window, condition): # update_window_remove(window, arr[left]) left += 1 # 3. Update result using current valid window [left, right] result = max(result, right - left + 1) return result ``` This maps directly to most **“longest/shortest with condition”** problems: - Unique characters - At most k distinct - Sum ≤ target (positive numbers) #### Fixed-size sliding window template ```python def sliding_window_fixed(arr, k: int) -> int: window_sum = 0 best = float("-inf") for right, value in enumerate(arr): window_sum += value # element enters if right >= k - 1: # window hit size k best = max(best, window_sum) # process current window window_sum -= arr[right - k + 1] # element leaves return best ``` Here, there’s no explicit validity check; the constraint is purely the **fixed window size**. ### Java #### Variable-size sliding window template ```java int slidingWindowVar(int[] nums) { int left = 0; int result = 0; Map window = new HashMap<>(); for (int right = 0; right < nums.length; right++) { int val = nums[right]; window.put(val, window.getOrDefault(val, 0) + 1); // expand while (!isValid(window)) { // shrink until valid int leftVal = nums[left]; window.put(leftVal, window.get(leftVal) - 1); if (window.get(leftVal) == 0) { window.remove(leftVal); } left++; } result = Math.max(result, right - left + 1); // update } return result; } ``` #### Fixed-size sliding window template ```java int slidingWindowFixed(int[] nums, int k) { int windowSum = 0; int best = Integer.MIN_VALUE; for (int right = 0; right < nums.length; right++) { windowSum += nums[right]; // expand if (right >= k - 1) { best = Math.max(best, windowSum); // process window windowSum -= nums[right - k + 1]; // shrink } } return best; } ``` ### JavaScript #### Variable-size sliding window template ```javascript function slidingWindowVar(arr) { let left = 0; let result = 0; const window = new Map(); // or Set / object for (let right = 0; right < arr.length; right++) { const val = arr[right]; window.set(val, (window.get(val) || 0) + 1); // expand while (!isValid(window)) { // shrink until valid const leftVal = arr[left]; window.set(leftVal, window.get(leftVal) - 1); if (window.get(leftVal) === 0) { window.delete(leftVal); } left++; } result = Math.max(result, right - left + 1); // update } return result; } ``` #### Fixed-size sliding window template ```javascript function slidingWindowFixed(arr, k) { let windowSum = 0; let best = -Infinity; for (let right = 0; right < arr.length; right++) { windowSum += arr[right]; // expand if (right >= k - 1) { best = Math.max(best, windowSum); // process window windowSum -= arr[right - k + 1]; // shrink } } return best; } ``` Once you can write these templates from memory, solving most sliding window interview questions becomes a matter of: - Choosing the right **state** (sum, count, frequency map / counter, deque) - Implementing the **validity check** correctly --- ## Sliding Window in Action: Step-by-Step Examples Let’s walk through three canonical sliding window LeetCode problems, with diagrams and pitfalls. ### Example 1: Longest Substring Without Repeating Characters (LeetCode 3) **Problem**: Given a string `s`, return the length of the **longest substring** without repeating characters. This is the poster child for **variable-size sliding window**: - Window type: substring (string → contiguous) - Invariant: “no character appears more than once in the window” - State: a **set** or frequency map of characters #### Window evolution For `s = "abcabcbb"`: ```text Step left right window action ----- ---- ----- -------- ---------------------------- 0 0 0 "a" add 'a', max_len = 1 1 0 1 "ab" add 'b', max_len = 2 2 0 2 "abc" add 'c', max_len = 3 3 0 3 "abca" 'a' repeats → shrink 4 1 3 "bca" after removing left 'a', valid ... ``` #### Python solution ```python def lengthOfLongestSubstring(s: str) -> int: left = 0 seen = set() best = 0 for right, ch in enumerate(s): # shrink until window has no duplicate of ch while ch in seen: seen.remove(s[left]) left += 1 # now safe to expand seen.add(ch) best = max(best, right - left + 1) return best ``` Key points: - Shrink loop is **while**, not `if`, because you may need to remove **multiple** characters. - The **window invariant** is: “`seen` contains each char in `s[left:right+1]` at most once.” - Complexity: `O(N)` time, `O(min(N, M))` space where `M` is alphabet size. Common pitfalls: - Forgetting to remove characters from `seen` when shrinking - Using `right - left` instead of `right - left + 1` For more on string-specific nuances, see [Sliding Window: Substrings vs Subarrays — What’s the Difference?](/leetcode-pattern/sliding-window/substring-vs-subarray-sliding-window). --- ### Example 2: Max Consecutive Ones III (LeetCode 1004) **Problem**: Given a binary array `nums` and an integer `k`, return the maximum number of **consecutive 1s** in the array if you can flip at most `k` zeros. This is a classic “**at most k**” sliding window: - Invariant: “window has **at most k zeros**” - State: count of zeros in the current window #### Intuition Instead of thinking “flip k zeros”, think: > Find the longest window that contains at most k zeros. > Inside that window, flip all zeros to 1 and you get the answer. #### JavaScript solution ```javascript function longestOnes(nums, k) { let left = 0; let zeros = 0; let best = 0; for (let right = 0; right < nums.length; right++) { if (nums[right] === 0) zeros++; // expand while (zeros > k) { // shrink until valid if (nums[left] === 0) zeros--; left++; } best = Math.max(best, right - left + 1); } return best; } ``` Key debugging notes: - The **validity condition** is the count of zeros, not the count of ones. - Window invariant: after the shrink loop, `zeros ≤ k`. - This pattern generalizes to many “at most k distinct / at most k bad elements” problems. --- ### Example 3: Minimum Window Substring (LeetCode 76) **Problem**: Given strings `s` and `t`, return the minimum window substring of `s` that contains all the characters of `t` (with multiplicity). If no such substring exists, return empty string. This is a **shrink-to-fit** sliding window: - You expand until the window first becomes **valid** - Then shrink from the left to find the **smallest** valid window #### State and invariant - `need[c]`: how many of character `c` we still require - `have`: how many characters from `t` are currently satisfied - Invariant after shrinking: “window contains all characters required by `t`” #### Python solution ```python from collections import Counter def minWindow(s: str, t: str) -> str: if not s or not t: return "" need = Counter(t) window = Counter() required = len(need) formed = 0 left = 0 best_len = float("inf") best = (0, 0) for right, ch in enumerate(s): window[ch] += 1 if ch in need and window[ch] == need[ch]: formed += 1 # shrink while window is valid while formed == required: if right - left + 1 < best_len: best_len = right - left + 1 best = (left, right) left_ch = s[left] window[left_ch] -= 1 if left_ch in need and window[left_ch] < need[left_ch]: formed -= 1 left += 1 if best_len == float("inf"): return "" start, end = best return s[start : end + 1] ``` Common pitfalls: - Mismanaging `formed` (incrementing or decrementing at the wrong time) - Updating the result **before** ensuring the window is valid This problem is a great capstone for the sliding window pattern and appears frequently in **sliding window interview questions**. --- ## Advanced Techniques & Variations Once you’re comfortable with basic sliding window examples, you’ll see richer variations that combine counters, maps, and sometimes extra data structures. ### “At most k distinct” and “exactly k distinct” The pattern for “**at most k distinct characters**” is: - Use a **frequency map / counter** - Shrink while `distinct_count > k` ```python def longest_substring_at_most_k_distinct(s: str, k: int) -> int: left = 0 freq = {} best = 0 for right, ch in enumerate(s): freq[ch] = freq.get(ch, 0) + 1 while len(freq) > k: left_ch = s[left] freq[left_ch] -= 1 if freq[left_ch] == 0: del freq[left_ch] left += 1 best = max(best, right - left + 1) return best ``` For “**exactly k distinct**”, use: > `exactlyK(k) = atMostK(k) - atMostK(k - 1)` This trick appears often in advanced sliding window LeetCode problems like “Subarrays with K Different Integers”. ### Target sum variations When the array contains **only non-negative** numbers: - “Longest subarray with sum ≤ target” - “Shortest subarray with sum ≥ target” You can use sliding window because the sum is **monotonic**: - Expanding the window can only **increase** the sum - Shrinking can only **decrease** the sum When the array has **negative numbers**, monotonicity breaks. Use **prefix sum** instead; see [Sliding Window for Negative Numbers — Why It Breaks & What to Do Instead](/leetcode-pattern/sliding-window/sliding-window-negative-numbers) and [Sliding Window vs Prefix Sum](/leetcode-pattern/sliding-window/sliding-window-vs-prefix-sum). ### Sliding window with sorting (rare) Occasionally you’ll see problems where: - You sort the array (or a derived array) - Then apply a sliding window on the sorted sequence Example: “Longest subarray where difference between min and max ≤ limit” can be done with sorted structure + window, or with deques on the original array. Rule of thumb: - Sorting usually implies **two pointers** or **binary search** - Use sliding window on sorted data only when you still reason about **contiguous runs** and can maintain the state in O(1)/logN. ### Sliding window with deques (monotonic queues) For problems like **Sliding Window Maximum (LeetCode 239)**: - You want max or min over every window of size k - Recomputing max on each shift is O(k) → O(Nk) Use a **monotonic deque**: ```python from collections import deque def sliding_window_max(nums, k): dq = deque() # stores indices, values decreasing result = [] for right, val in enumerate(nums): # drop smaller elements from back while dq and nums[dq[-1]] <= val: dq.pop() dq.append(right) # drop elements falling out of window if dq[0] <= right - k: dq.popleft() if right >= k - 1: result.append(nums[dq[0]]) # front is max return result ``` This pattern generalizes to: - Sliding minimum - Maintaining max difference under constraints ### “Bucket shrinking” variants Sometimes you shrink the window by **more than one step at a time** using extra information: - Precomputed prefix sums - Pre-bucketed indices These show up in performance-optimized variants, but the conceptual pattern is the same: - Keep a contiguous window - Maintain a correct invariant - Use additional information to move `left` in fewer steps ### “Resetting window” patterns Not all problems use a smooth expand/shrink. Example: if the window becomes impossible to repair (e.g., encountering a hard barrier character), you may: - Jump `left` directly to `right + 1` - Reset state entirely This is still sliding window, but the **shrink** step is a full reset. You’ll see variants of this in some substring and product-based problems. --- ## Debugging Sliding Window: A Senior Engineer’s Checklist If you’ve ever had a window that “doesn’t shrink” or a result off by one, you’re not alone. Use this sliding window debugging checklist when your solution misbehaves and to avoid common **sliding window pitfalls**. For deep dives on specific pitfalls, see: - [Sliding Window Off-by-One Errors — How to Fix Them](/leetcode-pattern/sliding-window/sliding-window-off-by-one-errors) - [Why Your Sliding Window "Shrinks Wrong" — A Debugging Guide](/leetcode-pattern/sliding-window/sliding-window-debugging-shrinks-wrong) - [Common Sliding Window Mistakes (And How to Fix Them)](/leetcode-pattern/sliding-window/common-sliding-window-mistakes) ### 1. Off-by-one window size Symptom: - Your answer is consistently 1 too big or too small - Edge cases like length 1 or empty input fail Checklist: - Window size must be `right - left + 1`, not `right - left` - When using fixed-size windows, ensure you start processing only when `right >= k - 1` ### 2. Misordered expand / shrink Symptom: - You shrink before adding the new element, or update the answer on an invalid window Checklist: - Standard order for variable-size windows: 1. Add element at `right` (expand) 2. While invalid → remove from `left` (shrink) 3. Now window [left, right] is valid → update answer If you break this order, your **window invariant** becomes hard to reason about. ### 3. Wrong invariant Symptom: - You don’t know when to stop shrinking - The loop condition is “close but not quite right” Checklist: - State your invariant in English first: - “After shrinking, the window must contain **at most k zeros**” - “After shrinking, the window must contain **all characters of t**” - Write the condition that is **true after the shrink loop**, not before it. - Your shrink loop should be `while (!invariant)` or `while (invalid)`. ### 4. Negative numbers in sum problems Symptom: - Sliding window works on sample tests but fails on edge cases with negatives Checklist: - If the array can contain **negative numbers** and you’re reasoning about **sum or product**, sliding window may be invalid. - Prefer **prefix sum** for “sum == k” or “count subarrays with sum k”. - See: - [Sliding Window for Negative Numbers](/leetcode-pattern/sliding-window/sliding-window-negative-numbers) - [When NOT to Use Sliding Window](/leetcode-pattern/sliding-window/when-not-to-use-sliding-window) ### 5. Complex window state Symptom: - You’re maintaining multiple maps/counters and can’t reason about correctness Checklist: - Ask: “What is the **minimum state** I need to test validity?” - Consolidate: - A single **frequency map / counter** for characters - A single `violations` or `formed` integer - If state feels like ad-hoc patchwork, revisit the problem explanation and derive the invariant again. ### 6. Condition evaluation timing Symptom: - You update `best` before or after the wrong operation, missing optimal windows Checklist: - For **maximum length** problems, you normally update after the shrink loop (when the window is valid and as large as possible). - For **minimum length** problems, you often update **inside** the shrink loop (each time you find a valid window and then try to shrink further). If this feels confusing, walk through a simple example by hand with a table of `left`, `right`, and window content. --- ## Sliding Window vs Two Pointers vs Prefix Sum Sliding window is often confused with two pointers and prefix sum. Let’s clarify. ### Conceptual differences - **Sliding Window**: - Maintains a **contiguous window** `[left, right]` - Both pointers move forward (left never goes backwards) - Focuses on properties of the **entire interval** - **Two Pointers** (classic): - Often uses pointers at opposite ends, moving towards each other - Used for **pair/triplet** problems, often on **sorted arrays** - Doesn’t necessarily care about elements between the pointers - **Prefix Sum**: - Precomputes cumulative sums - Excellent for **sum equals k** or range queries, including with **negative numbers** - Often combined with hash maps for O(N) subarray sum counts ### Decision matrix | Pattern | Best When | Typical Keywords | Example Problem | |----------------|---------------------------------------------------------------------------|-----------------------------------------------|------------------------------------------------------| | Sliding Window | Contiguous subarray/substring, optimize window size/value, expand/shrink | longest, shortest, at most k, consecutive | Longest substring w/o repeats, max consecutive ones | | Two Pointers | Sorted input, pair/triplet endpoints, no need for all in-between | pair sum, triplet, container, partition | Two Sum II, 3Sum, Container With Most Water | | Prefix Sum | Sum equals k, negative numbers allowed, count subarrays | subarray sum, equal to k, range sum queries | Subarray Sum Equals K, longest subarray sum = k | When in doubt: - If it says **contiguous** and **optimize window** → sliding window - If it says **pairs/triplets** and **sorted** → two pointers - If it says **sum equals k** and negatives exist → prefix sum For more side-by-side examples, read: - [Sliding Window vs Two Pointers](/leetcode-pattern/sliding-window/sliding-window-vs-two-pointers) - [Sliding Window vs Prefix Sum](/leetcode-pattern/sliding-window/sliding-window-vs-prefix-sum) --- ## Best Sliding Window LeetCode Problems (Ranked) You don’t need to solve every sliding window LeetCode problem. You need the **right** ones. Here’s a condensed roadmap; a full list with explanations and variations lives in [Top Sliding Window Problems on LeetCode (Ranked)](/leetcode-pattern/sliding-window/top-sliding-window-problems-leetcode-ranked). ### Easy (build the template) - **Maximum Average Subarray I (643)** — fixed-size sliding window - **Max Consecutive Ones (485)** — simple variable window over a binary array - **Minimum Size Subarray Sum (209)** — shortest window with sum ≥ target (positive numbers) Skills: - Implement fixed-size and variable-size templates - Get comfortable with **expand and shrink** mechanics and window validity ### Medium (core interview set) - **Longest Substring Without Repeating Characters (3)** — distinct chars - **Permutation in String (567)** — fixed-size window with frequency map - **Find All Anagrams in a String (438)** — collect all valid windows - **Longest Repeating Character Replacement (424)** — clever use of max frequency - **Fruit Into Baskets (904)** — “at most k distinct” disguised as a story - **Minimum Window Substring (76)** — full shrink-to-fit pattern Skills: - Managing frequency maps and counters cleanly - Handling “at most k” vs “exactly k” variants ### Hard (advanced windows) - **Sliding Window Maximum (239)** — monotonic deque - **Substring with Concatenation of All Words (30)** — window over word-sized chunks - **Sliding Window Median (480)** — sliding window + heaps As you solve these, keep your **sliding window template** side-by-side and consciously map each problem onto it. --- ## Common Interview Questions About Sliding Window Interviewers love to probe not just *that* you can code the pattern, but *why* it works. Here are common sliding window interview questions and concise answers. ### “How do I know when to shrink the window?” Define a **validity condition** and shrink while it’s violated. Examples: - “At most k zeros”: shrink while `zeros > k` - “At most k distinct characters”: shrink while `len(freq) > k` - “Window contains all chars of t”: shrink while window remains valid (for minimum problems) The core rule: > Shrink as long as the window is **invalid** (or can still stay valid while getting smaller, for minimum problems). ### “How do I detect window validity?” Tie validity to a **simple state and invariant**: - Use a frequency map and a `distinct` count - Use a sum and a threshold - Use a `formed` counter for “all requirements met” Your job is to design state so that: - Testing validity is O(1) - The state can be updated cheaply on expand/shrink ### “Why does sliding window run in O(N) if there’s a nested loop?” Because each pointer only moves **forward**: - `right` increments from 0 to N - 1 once - `left` also increments from 0 to N - 1 once Even though you see a `for` + `while`, across the entire algorithm each element is added and removed at most once. That’s why it’s linear. ### “Does sliding window work with negative numbers?” It depends: - If your window state is based on **counts or distinct elements**, negatives are irrelevant. - If you’re reasoning about **sum with negatives**, the usual greedy logic breaks: - Expanding can make the sum go down - Shrinking can make the sum go up For these, prefer prefix sums; see [Sliding Window for Negative Numbers](/leetcode-pattern/sliding-window/sliding-window-negative-numbers). ### “When should I NOT use sliding window?” Avoid sliding window when: - The problem is about **subsequences** (non-contiguous) → usually DP - You need **all combinations** or complex global decisions → backtracking / DP - The window state can’t be updated in O(1) or amortized O(1) - Sum-based problems with **mixed-sign numbers** require more global reasoning For a dedicated breakdown of failure modes and alternatives, see [When NOT to Use Sliding Window](/leetcode-pattern/sliding-window/when-not-to-use-sliding-window) and [Sliding Window for Negative Numbers](/leetcode-pattern/sliding-window/sliding-window-negative-numbers). --- ## Final Summary and Next Steps Sliding window is one of the highest-leverage patterns in algorithm interviews: - It turns many brute-force O(N²) scans into clean **O(N) window techniques** - It’s the backbone for dozens of sliding window LeetCode problems - It forces you to think in terms of **invariants, validity, and state** ### What to memorize - The **variable-size sliding window template** in your main language - The **fixed-size sliding window** variation - How to express the **window invariant** in one sentence - The core pitfalls: - Off-by-one window size - Misordered expand/shrink - Wrong or missing validity checks - Negative numbers breaking monotonicity ### Practice plan 1. Read the focused intuition guide: [Sliding Window Intuition Explained Step-by-Step](/leetcode-pattern/sliding-window/sliding-window-intuition-explained) 2. Drill the templates with the curated list: [Top Sliding Window Problems on LeetCode (Ranked)](/leetcode-pattern/sliding-window/top-sliding-window-problems-leetcode-ranked) 3. Review pitfalls as you debug: - [Off-by-One Errors](/leetcode-pattern/sliding-window/sliding-window-off-by-one-errors) - [Debugging Shrink Logic](/leetcode-pattern/sliding-window/sliding-window-debugging-shrinks-wrong) - [Common Sliding Window Mistakes](/leetcode-pattern/sliding-window/common-sliding-window-mistakes) 4. Stretch into advanced territory: - [Sliding Window vs Two Pointers](/leetcode-pattern/sliding-window/sliding-window-vs-two-pointers) - [Sliding Window vs Prefix Sum](/leetcode-pattern/sliding-window/sliding-window-vs-prefix-sum) - [Sliding Window in 2D / Matrix Problems](/leetcode-pattern/sliding-window/sliding-window-2d-matrix-problems) ### How LeetCopilot fits in The fastest way to internalize the sliding window pattern is **deliberate practice**: - See many variants of **window invariants** (“at most k”, “exactly k”, “contains all”, etc.) - Get instant feedback when you introduce a subtle off-by-one or shrink-order bug LeetCopilot can: - Surface the right **pattern-based problems** at the right difficulty - Track which subpatterns you struggle with (e.g., “at most k distinct”, deques, 2D) - Nudge you toward the next best problem instead of random grinding Finally, remember: sliding window is just **one cluster** in your patterns toolbox. Use the main [LeetCode Patterns hub](/leetcode-pattern) and the [Sliding Window cluster](/leetcode-pattern/sliding-window) to explore related techniques and keep building your mental library.

Topics

Sliding Window