Some coding problems seem innocent, “find the max sum,” “check if this pattern exists,” “find the smallest substring that meets a condition.” You might start by reaching for nested loops or brute force... until the timeouts hit or your code gets ugly. That’s where the **Sliding Window** pattern comes in. This pattern is one of the most **powerful tools** for optimizing problems that involve **contiguous sequences**, whether you're working with strings, arrays, or streams. --- ## What Is the Sliding Window Pattern? The **Sliding Window** technique involves using a **moving window** (defined by two pointers) to efficiently track information across a subsection of data. Instead of recalculating or rechecking everything repeatedly, you **slide the window forward**, updating only what changes. ### Simple Definition: > Keep track of a portion of the input that moves forward with each step, only expanding or shrinking when needed. --- ## Why Use Sliding Window? ✅ **Efficient**: Reduces time complexity from `O(n²)` to `O(n)` in many cases ✅ **Elegant**: Keeps code clean and easy to debug ✅ **Versatile**: Works on strings, arrays, substrings, and subarrays ✅ **Interview Favorite**: Shows up constantly in real coding interviews --- ## Real-World Analogy Imagine you’re reading a book through a small rectangular cutout, a window. - You can only see a few words at a time. - As you read, you **slide the window** across the page. - You don’t re-read everything, just the new word as it comes in and the old one as it leaves. This is what sliding window does in code: *Focus on what changes, ignore what stays the same.* --- ## How Is This Different From Two Pointers? Sliding Window **builds on** the Two Pointers pattern. In both: - You have two indices tracking a range - One or both move as conditions change But Sliding Window typically: - Focuses on **ranges or substrings** (sums, counts, conditions) - Uses **data structures** to track internal state (e.g. hashmaps, sets) - Expands and shrinks the window dynamically > Think of it this way: > Two Pointers track positions. > Sliding Window tracks state inside a range. --- ## When Should You Reach for Sliding Window? Use this pattern when the problem asks for: | Problem Type | Clue That It’s Sliding Window | |------------------------------------------|--------------------------------------------| | Longest/shortest substring or subarray | "length of..." or "minimum window that..." | | Fixed-size range calculations | "window of size k", "max sum of k elements"| | Real-time pattern matching | "check if a permutation exists..." | | Shrinking/growing boundaries | "as long as condition is met" | | Avoiding recomputation | "...without starting over each time" | --- ## What You’ll Learn in This Guide In the rest of this post, we'll break down: - The difference between **fixed-size** and **dynamic** windows - Core templates you can reuse - Visual diagrams that show how the window moves - Real Leetcode-style problems with clear explanations - Common mistakes to avoid - How to build your intuition to apply this pattern anywhere Let’s get into it, and stop solving `O(n²)` problems that were always meant to be `O(n)`. --- ## Fixed vs Dynamic Sliding Windows The Sliding Window pattern comes in two major flavors, and choosing the right one can make all the difference in how clean and efficient your solution is. Let’s break them down. --- ### Fixed-Size Sliding Window This is the **simplest form** of the pattern. - The window has a **constant size** (often `k`) - You move the window forward one step at a time - You only track **what enters and leaves** the window --- #### When to Use It Look for keywords like: - “Subarray of size `k`” - “Maximum/minimum sum of `k` elements” - “Window of fixed length” > If the problem gives you a fixed `k`, it's a good sign that this is the way to go. --- #### Template: Fixed Window ```js let sum = 0; // Initialize first window for (let i = 0; i < k; i++) { sum += arr[i]; } let max = sum; // Slide the window for (let i = k; i < arr.length; i++) { sum = sum - arr[i - k] + arr[i]; max = Math.max(max, sum); } ``` --- #### Real-World Analogy Imagine tracking the **temperature every hour** for 24 hours, and you want to find the **hottest 3-hour period**. You don’t restart counting for every new block of 3 hours, you just: - Subtract the earliest hour as you slide forward - Add the new hour coming in That's a fixed-size sliding window. --- ### Dynamic-Size Sliding Window Dynamic windows **grow and shrink** depending on constraints. - The window starts small (even empty) - You expand it (`right++`) until a condition is broken - Then shrink it (`left++`) until the condition is valid again > These are more flexible, and more powerful, but require more logic. --- #### When to Use It Look for phrases like: - “Longest substring with no repeats” - “Smallest window that contains...” - “As long as condition is true...” - “At most/at least `k` unique characters” These problems **don’t give you a size upfront**, instead, you must **adapt the window** based on logic. --- #### Template: Dynamic Window ```js let left = 0; for (let right = 0; right < s.length; right++) { // expand window with s[right] // update frequency, count, or state while (window is invalid) { // shrink from the left // update frequency/state accordingly left++; } // optionally update result } ``` --- #### Real-World Analogy You're watching videos in a playlist, but can only watch for 10 minutes total. - You **add videos** until you go over time - Then you **remove older ones** until you're back under the limit - At each step, you're tracking how long the current playlist is That’s a dynamic sliding window, **expanding and contracting** based on rules. --- ## Summary: How to Choose | Feature | Fixed Window | Dynamic Window | |-------------------------------|---------------------------|-------------------------------| | Window size | Constant (usually `k`) | Expands/shrinks dynamically | | Common problems | Max sum, avg of size `k` | Substrings, pattern matching | | Loop logic | For-loop + index math | Two pointers with conditions | | State tracking | Simple (sum, max) | Often uses hashmap/set | | Performance | Always `O(n)` | Often `O(n)` with conditions | --- ## What’s Next? Now that you understand the **two types of windows**, the next step is to learn the **core templates** and walk through **real problems**, fixed first, then dynamic. By the end, you’ll be sliding through problems like a pro. Let’s start with a classic fixed window example: *“Maximum sum of a subarray of size `k`”* --- ## Example 1: Maximum Sum of a Subarray of Size `k` Let’s start with a **fixed-size sliding window** problem, clean, elegant, and a perfect showcase for why this pattern is powerful. --- ### Problem > Given an array of integers `nums` and an integer `k`, find the **maximum sum** of any contiguous subarray of size `k`. #### Example: ```js Input: nums = [2, 1, 5, 1, 3, 2], k = 3 Output: 9 // Subarray with max sum is [5, 1, 3] ``` --- ## Brute Force First A naive solution would be to check **every possible subarray of length `k`** using two nested loops: ```js function maxSubarraySumBrute(nums, k) { let max = -Infinity; for (let i = 0; i <= nums.length - k; i++) { let sum = 0; for (let j = i; j < i + k; j++) { sum += nums[j]; } max = Math.max(max, sum); } return max; } ``` **Time Complexity:** `O(n × k)`, this will slow down quickly as input grows. --- ## Sliding Window Solution Here’s the insight: > You don’t need to recalculate the sum from scratch every time. > Just **add the new number** and **subtract the number that just left the window**. --- ### Code: ```js function maxSubarraySum(nums, k) { let windowSum = 0; let maxSum = -Infinity; // Build the first window for (let i = 0; i < k; i++) { windowSum += nums[i]; } maxSum = windowSum; // Slide the window for (let i = k; i < nums.length; i++) { windowSum = windowSum - nums[i - k] + nums[i]; maxSum = Math.max(maxSum, windowSum); } return maxSum; } ``` --- ### How It Works: Let's take the array: `[2, 1, 5, 1, 3, 2]` with `k = 3`. 1. First window: `2 + 1 + 5 = 8` 2. Slide window right: - Subtract `2` (leftmost of old window) - Add `1` (new element) - New window sum: `8 - 2 + 1 = 7` 3. Continue: - Subtract `1`, add `3` → sum = `9` → max so far - Subtract `5`, add `2` → sum = `6` 4. Done. Maximum was `9`. --- ### Visual (Described): ``` Window 1: [2, 1, 5] → sum = 8 Window 2: [1, 5, 1] → sum = 7 Window 3: [5, 1, 3] → sum = 9 ✅ Window 4: [1, 3, 2] → sum = 6 ``` Each time, you **remove one number** and **add one number**, constant-time update. --- ### Time & Space Complexity | Metric | Complexity | |----------------|-----------------| | Time | O(n) | | Space | O(1) | - We touch each element **exactly once** after the first window. - No extra space used beyond a few variables. --- ### Real-World Applications | Use Case | Why Sliding Window Helps | |--------------------------------------------|--------------------------------------------| | Sensor data smoothing | Track spikes or drops in rolling averages | | Analytics (e.g. visits per hour) | Real-time reporting for time windows | | Financial modeling | Max gain/loss over fixed intervals | | Game mechanics | Score tracking in last X moves | --- ### Pattern Recognition If you see: - “max/min/avg of every subarray of size `k`” - “in windows of fixed length” - “rolling sum/average” That’s **fixed sliding window territory**. --- ## Coming Up Next Let’s now explore something more flexible: **“Longest substring without repeating characters”**, a dynamic sliding window where the size changes depending on content inside the window. --- ## Example 2: Longest Substring Without Repeating Characters Time to level up: let’s move into **dynamic window territory**. This problem introduces a window that **expands and contracts based on character constraints**, and it’s a staple in technical interviews. --- ### Problem > Given a string `s`, return the length of the **longest substring** without repeating characters. #### Example: ```js Input: s = "abcabcbb" Output: 3 Explanation: "abc" is the longest substring without repeating characters. ``` --- ## Key Insight We want to scan through the string and track **the current window of unique characters**. - If the character is not a repeat → expand the window (move `right`) - If it’s a repeat → shrink the window (move `left`) until valid This is **dynamic** because the window size is not fixed, it adjusts based on the characters inside it. --- ### Code: ```js function lengthOfLongestSubstring(s) { let left = 0; let maxLen = 0; let seen = new Set(); for (let right = 0; right < s.length; right++) { while (seen.has(s[right])) { seen.delete(s[left]); left++; } seen.add(s[right]); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } ``` --- ### How It Works Take the input string: `"abcabcbb"` 1. Start with an empty set `seen = {}` and `left = 0` 2. Move `right` one character at a time: - Add character to `seen` - If the character already exists, remove from the left until it's unique again 3. Track `maxLen = right - left + 1` at each valid step --- ### Visual Walkthrough ``` String: a b c a b c b b ↑ left ↑ right seen = {a, b, c} → duplicate 'a' found → shrink from left: remove 'a', then continue ``` At each step, the window **only contains unique characters**. The moment we see a repeat, we shrink it until the condition is valid again. --- ### Time & Space Complexity | Metric | Complexity | |----------------|-------------------| | Time | O(n) | | Space | O(k) (distinct chars) | - Every character is **added and removed at most once** from the set - Efficient and clean, exactly what interviewers want to see --- ### Common Pitfalls - ❌ Forgetting to remove from the set → infinite loop - ❌ Confusing substring vs subsequence (they must be **contiguous**) - ❌ Misusing indexes in `right - left + 1`, easy off-by-one trap - ❌ Not handling empty string (`"" → 0`) --- ### What This Problem Tests | Concept | Why It’s Important | |-----------------------------------|---------------------------------------------| | Window expansion & contraction | Core dynamic logic | | Using a Set to track uniqueness | Data structure fluency | | Real-time constraint checking | Common in stream/buffer handling | | Pointer logic and conditions | Avoiding overlap, infinite loops, bugs | --- ### Real-World Applications - Text editors: highlight duplicate-free tokens - Password validators: longest non-repeating sequence - Input sanitizers: flag patterns of repeated characters - Game design: longest "combo streak" without reset --- ## Pattern Recognition If you see: - “Longest substring that meets condition” - “Without repeating / with at most X of something” - “As long as...” That’s a **dynamic sliding window** with condition tracking. --- ## Coming Up Next Now that we’ve handled dynamic windows for uniqueness... Let’s go one level deeper and handle **frequency-based windows**. Up next: **Minimum Window Substring**, one of the most powerful dynamic window patterns in interviews. --- ## Example 3: Minimum Window Substring This one’s a bit more advanced, but it’s a **real interview classic**. It combines **dynamic window resizing** with **frequency maps** to solve a substring optimization problem. And when you get it, you'll feel like you’ve leveled up your algorithm game. --- ### Problem > Given two strings `s` and `t`, return the **smallest window** in `s` that contains all the characters of `t` (including duplicates). > If no such window exists, return `""`. #### Example: ```js Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" ``` --- ### Key Insight - This is not just about **uniqueness** (like in the last example) - You need to match the **frequency of each character in `t`** - The window needs to **grow until all required characters are included**, then **shrink as much as possible** --- ## How Do We Track the Requirement? - Use a **hashmap** to count how many times each character must appear - Keep a second hashmap (or counter) for what’s currently in the window - Only when **all required characters** are met does the window become “valid” --- ### Code: ```js function minWindow(s, t) { if (t.length > s.length) return ""; const need = {}; for (let char of t) { need[char] = (need[char] || 0) + 1; } let left = 0, right = 0; let count = 0; // matched characters let minLen = Infinity; let start = 0; const window = {}; while (right < s.length) { const char = s[right]; window[char] = (window[char] || 0) + 1; if (need[char] && window[char] === need[char]) { count++; } // Shrink window until it's invalid while (count === Object.keys(need).length) { if ((right - left + 1) < minLen) { minLen = right - left + 1; start = left; } const leftChar = s[left]; window[leftChar]--; if (need[leftChar] && window[leftChar] < need[leftChar]) { count--; } left++; } right++; } return minLen === Infinity ? "" : s.substring(start, start + minLen); } ``` --- ### How It Works Using `s = "ADOBECODEBANC"` and `t = "ABC"`: 1. Expand the window (`right++`) and count characters in `window` 2. Once the current window contains all chars in `t`, try to **shrink from the left** 3. Keep track of the **smallest valid window** seen 4. Return the substring defined by that window --- ### Visual Overview ``` Initial state: left = 0, right = 0 window = {} need = {A:1, B:1, C:1} Expand → "A", "D", "O" ... until you include A, B, C → Then shrink → until window no longer valid → Track the shortest such window ``` --- ### Time & Space Complexity | Metric | Complexity | |----------------|---------------------| | Time | O(n + m) | | Space | O(n + m) | - `n = s.length`, `m = t.length` - You process each character in `s` at most twice (once when expanding, once when shrinking) - Two hashmaps: one for `need`, one for `window` --- ### Common Pitfalls | Mistake | Fix/Tip | |-------------------------------------|---------------------------------------------------| | Only checking presence, not counts | Use `count === need[char]` to match frequency | | Forgetting to shrink window | Always shrink when all required chars are matched| | Returning too early | Wait until the entire window is valid | | Off-by-one in substring boundaries | Use `s.substring(start, start + minLen)` | --- ### What This Problem Teaches You | Concept | Why It Matters | |-----------------------------|---------------------------------------------| | Tracking frequencies | Common in pattern and subset problems | | Shrinking windows optimally | Shows deep understanding of state logic | | Goal-based window logic | Applies to many constraint-style problems | | Advanced condition tracking | More realistic in real-world applications | --- ### Real-World Uses - Token/keyword highlighting: smallest range with all terms - Streaming data filters: matching frames, frameshift detection - Query engines: match full criteria in minimal space - NLP: entity resolution and span identification --- ## Pattern Recognition This is a **“smallest window that meets a condition”** problem: - You need the window to be as small as possible - You must track state internally with counts - You expand until valid, shrink until invalid Think: > Expand ➡️ Validate ➡️ Shrink ➡️ Optimize --- ### Deep Dive: Understanding the Minimum Window Substring Step-by-Step This is one of those problems that seems confusing until you walk through it slowly, and then suddenly it *clicks*. Let’s break it down line-by-line and explain how each part of the algorithm contributes to solving the problem. --- #### The Core Idea We need to find the **smallest substring in `s`** that **contains all characters in `t`**, including **their correct frequencies**. This isn’t just a uniqueness check, it’s a **multi-character frequency match**. --- ### Code Recap ```js function minWindow(s, t) { if (t.length > s.length) return ""; const need = {}; for (let char of t) { need[char] = (need[char] || 0) + 1; } let left = 0, right = 0; let count = 0; let minLen = Infinity; let start = 0; const window = {}; while (right < s.length) { const char = s[right]; window[char] = (window[char] || 0) + 1; if (need[char] && window[char] === need[char]) { count++; } while (count === Object.keys(need).length) { if ((right - left + 1) < minLen) { minLen = right - left + 1; start = left; } const leftChar = s[left]; window[leftChar]--; if (need[leftChar] && window[leftChar] < need[leftChar]) { count--; } left++; } right++; } return minLen === Infinity ? "" : s.substring(start, start + minLen); } ``` --- ### Breaking It Down Let’s go through the most important variables and logic: --- #### `need` object ```js const need = {}; for (let char of t) { need[char] = (need[char] || 0) + 1; } ``` This is a **frequency map of `t`**, showing how many times each character is required. Example: ```js t = "ABC" → need = { A: 1, B: 1, C: 1 } ``` If `t = "AABC"` → `need = { A: 2, B: 1, C: 1 }` --- #### `window` object This keeps track of the **current frequency** of each character **inside the current sliding window of `s`**. We compare `window[char]` against `need[char]` to know if we’ve met the requirement. --- #### `count` ```js if (need[char] && window[char] === need[char]) { count++; } ``` This counts **how many unique characters have been satisfied**. - For `t = "ABC"`, we want `count = 3` before we start shrinking - It only increases the first time a required character meets its frequency --- #### Expanding the Window ```js const char = s[right]; window[char] = (window[char] || 0) + 1; ``` - We include `s[right]` in the window - If this character is needed (exists in `need`) and the current window has just enough of it, we increment `count` This is our **expand phase**. --- #### When to Shrink the Window ```js while (count === Object.keys(need).length) { ``` - Only when **all required characters are satisfied** (correct frequency!) do we try to **shrink the window from the left** - This is where optimization happens: we want the window to be as **tight** as possible --- #### Updating the Minimum Window ```js if ((right - left + 1) < minLen) { minLen = right - left + 1; start = left; } ``` If we’ve found a valid window and it’s **smaller than the best so far**, we save it. --- #### Shrinking the Window ```js const leftChar = s[left]; window[leftChar]--; if (need[leftChar] && window[leftChar] < need[leftChar]) { count--; } left++; ``` - We remove `s[left]` from the window and move `left` forward - If removing this character makes the window **invalid** (i.e., now we have fewer than needed), we decrease `count` This ends the current valid window and returns to expanding. --- ### Mental Model: Expand → Validate → Shrink Here’s the mindset: 1. **Expand** until all required characters are satisfied 2. **Validate** the current window, it’s now a candidate 3. **Shrink** from the left to see if you can get a smaller valid window 4. Repeat until you’ve processed the whole string --- ### Step-by-Step Example (Visualized) Using `s = "ADOBECODEBANC"`, `t = "ABC"`: | Action | Window | Valid? | Explanation | |------------------------|------------------|--------|------------------------------------------| | Add A | A | ❌ | Have A, missing B & C | | Add D, O, B | ADOB | ❌ | Have A & B, still missing C | | Add E, C | ADOBEC | ✅ | All required chars found | | Shrink (remove A) | DOBEC | ❌ | Lost A → invalid | | Continue expanding... | CODEBA | ❌ | Still missing something | | Add N, C | CODEBANC | ✅ | Valid again | | Shrink to "BANC" | BANC | ✅ | Smallest valid window found | Final output: `"BANC"` --- ### Why This Problem Matters - Tests your ability to track dynamic state - Combines string manipulation with hashmap logic - Forces you to control expansion and contraction in tandem - Mirrors real-world use cases like pattern recognition, NLP, and search --- ### TL;DR > This isn’t about just finding any window, it’s about **balancing completeness with minimal size**. If you understand how to: - Track frequencies - Know when a window is “valid” - Shrink windows without breaking the condition You now understand one of the **most powerful applications** of the sliding window pattern. --- ## Coming Up Next Let’s finish strong by reviewing: - What we’ve learned - Common mistakes across all window types - Recommended practice problems - Encouragement to make sliding window second nature --- ## Sliding Window Recap: What You’ve Learned You’ve just built one of the most important tools in your algorithmic toolkit. The **Sliding Window Pattern** turns many “brute force” problems into elegant `O(n)` solutions by maintaining **context over a moving range** of elements. --- ### Core Takeaways | Concept | Summary | |------------------------------|-------------------------------------------------------------------------| | What is a sliding window? | A range (window) defined by two pointers that moves across the input | | Fixed-size window | Used for problems like “max sum of subarray of size k” | | Dynamic-size window | Grows/shrinks based on conditions like uniqueness or frequency matching | | When to use it | Contiguous subarrays/substrings + optimization (max, min, match, etc.) | | How it improves performance | Reduces unnecessary rework, from `O(n²)` to `O(n)` | | Key patterns | Expand ➡️ Validate ➡️ Shrink ➡️ Optimize | --- ## Common Pitfalls to Avoid | Mistake | Fix / Why It Happens | |--------------------------------------|--------------------------------------------------------------------| | Forgetting to move pointers | Infinite loop or stale state, always advance `left` or `right` | | Incorrect window size calculation | Double-check: is it `right - left` or `right - left + 1`? | | Mismanaging frequency counts | Use objects (hashmaps) to track entries accurately | | Not shrinking window properly | Can cause overcounts or bloated result | | Misidentifying window boundaries | `substring(start, start + len)` → common off-by-one error | | Using global variables by accident | Always reset per test case if solving on Leetcode/HackerRank | > Pro Tip: Add console logs like `left`, `right`, and `window state` when debugging. --- ## Practice Problems (Apply What You Learned) | Difficulty | Problem Name | Platform | Type | |------------|---------------------------------------------|---------------|------------------| | Easy | Max Sum of Subarray of Size K | Leetcode | Fixed | | Medium | Longest Substring Without Repeating Chars | Leetcode #3 | Dynamic + Set | | Medium | Permutation in String | Leetcode #567 | Fixed + Frequency| | Hard | Minimum Window Substring | Leetcode #76 | Dynamic + Map | | Hard | Count Substrings with At Most K Distinct | Leetcode #992 | Advanced Dynamic | | Medium | Fruits into Baskets | Leetcode #904 | Shrinking Window | --- ## Sliding Window vs Two Pointers: Quick Refresher | Feature | Two Pointers | Sliding Window | |--------------------------|--------------------------|-------------------------------| | Use case | Comparison, symmetry | Subarray/substring conditions | | Movement | Both ends, same/diff pace| One grows, the other shrinks | | Size | Varies freely | Tracked, often constrained | | Tracking | Often no state | Tracks sum, count, frequency | | Typical structure | `while (left < right)` | `while (condition) { shrink }`| --- ## Final Words: Making Sliding Window Second Nature Sliding Window isn’t just a pattern, it’s a **mental model**. You’ve gone from simple fixed-range scans to dynamic window juggling with frequency maps. That’s a serious leap forward in problem-solving power. The key now is: - Keep practicing until the **“expand → validate → shrink”** flow becomes instinctual. - Try solving a few problems **without looking at the code first**, just walk through them with pen and paper. - Focus on **why** you're adjusting the window, not just how. > “Great code isn’t just written, it’s reasoned out.” > The Sliding Window pattern gives you the reasoning tools to solve problems cleanly, efficiently, and confidently. --- ## What’s Next? If you enjoyed this guide, the next patterns in your algorithm journey should be: - **Prefix Sums & Frequency Maps** — great for range queries and optimized counting - **Binary Search on Answer Space** — powerful for decision-making optimization - **Two Heaps / Monotonic Queues** — next-level versions of window-based thinking - **Graph Patterns & BFS/DFS** — for exploring connections and state transitions --- ## Thanks for Reading If this helped you level up your understanding of Sliding Window, share it with a friend or save it for your prep sessions. Practice builds pattern recognition. Pattern recognition builds confidence. Confidence gets you the offer. **Now go slide into your next coding session like a pro.** ---

Problem Solving Patterns: Sliding Window, Made Simple