Skip to main content

🪟 Sliding Window

One-line summary: Move a window over the input to solve subarray/substring problems in O(n) instead of O(n²).

💡 Core Concepts​

What is Sliding Window?​

Sliding Window is an optimization technique that transforms nested loops into a single loop by maintaining a window (subarray/substring) that slides across the input data.

Types of Sliding Window​

1️⃣ Fixed-Size Window​

  • Window size remains constant (exactly K elements)
  • Move window one position at a time
  • Perfect for: "Find max sum of K consecutive elements"

2️⃣ Dynamic/Variable Window​

  • Window size changes based on conditions
  • Expand right pointer to include new elements
  • Shrink left pointer when constraint is violated
  • Perfect for: "Find smallest subarray with sum ≥ target"

Key Sliding Window Properties​

  • Linear Time: Reduces O(n²) brute force to O(n)
  • Two Pointers: Uses left and right pointers to define window boundaries
  • State Tracking: Maintains window state (sum, count, frequency, etc.)
  • Constraint-Based: Window adjusts based on problem constraints

When to Use Sliding Window?​

✅ Perfect for:

  • Subarray/substring problems with contiguous elements
  • "Find maximum/minimum in window" problems
  • "Count subarrays with property X" problems
  • String pattern matching and anagram problems
  • "Longest/shortest subarray with condition" problems

❌ Not suitable for:

  • Non-contiguous subsequence problems
  • Problems requiring global optimization (use DP)
  • Tree/graph traversal problems
  • Overlapping Intervals: Sort by start time, merge when intervals[i].start <= lastEnd
  • Two Pointers: Similar concept but for different problem types
  • Prefix Sum: Can be combined with sliding window for range queries

📊 Visual Learning​

Sliding Window Technique OverEnhanced Sliding Window Animation​

Enhanced Visualization Features​

The enhanced animation demonstrates:

  • Dynamic window expansion and contraction with smooth visual transitions
  • Real-time sum calculation showing constraint validation
  • Color-coded status indicators (valid/invalid states)
  • Step-by-step algorithm phases with detailed explanations
  • Interactive pointer movements showing left and right boundary adjustments
  • Visual constraint checking highlighting when sum exceeds target

Original Sliding Window Flow Step-by-step visualization of how the sliding window moves across arrays to solve subarray problems

Dynamic Window Expansion​

Sliding Window Animation Interactive demonstration of window expansion and contraction based on problem constraints

Window Size Comparison​

Window Patterns Visual comparison between fixed-size and variable-size sliding window approaches

Memory Usage Optimization​

Sliding Window Memory Understanding space complexity and memory patterns in sliding window algorithms

Time & Space Complexity​

VariantTimeSpace
Fixed windowO(n)O(1) or O(k)
Dynamic windowO(n)O(k)
Merge intervalsO(n log n)O(n)

Common Patterns​

Fixed Window — Max Sum of K Elements​

function maxSumK(arr, k) {
  let windowSum = arr.slice(0, k).reduce((s, x) => s + x, 0);
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Dynamic Window — Longest Substring Without Repeat​

function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let left = 0,
    maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    if (seen.has(s[right])) left = Math.max(left, seen.get(s[right]) + 1);
    seen.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Merge Intervals​

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0]];
  for (const [s, e] of intervals.slice(1)) {
    if (s <= result[result.length - 1][1])
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], e);
    else result.push([s, e]);
  }
  return result;
}

Pitfalls​

  • Dynamic window: shrink from left until constraint is satisfied again — don't reset the window
  • Fixed window: slide by adding right element and subtracting element that just left

Practice Problems​

ProblemDifficultySolution
LC 121 — Best Time to Buy and Sell StockEasy
LC 219 — Contains Duplicate IIEasy
LC 643 — Maximum Average Subarray IEasy
LC 1004 — Max Consecutive Ones IIIEasy
LC 1456 — Maximum Number of Vowels in a Substring of Given LengthEasy
LC 1652 — Defuse the BombEasy
LC 1876 — Substrings of Size Three with Distinct CharactersEasy
LC 1984 — Minimum Difference Between Highest and Lowest of K ScoresEasy
LC 2269 — Find the K-Beauty of a NumberEasy
LC 2379 — Minimum Recolors to Get K Consecutive Black BlocksEasy
CC — Fixed Window Sum (FIXWIN)Easy
CC — Sliding Window Basic (SLIDEWIN)Easy
CC — Maximum Window (MAXWIN)Easy
LC 3 — Longest Substring Without RepeatingMedium
LC 56 — Merge IntervalsMedium
LC 567 — Permutation in StringMedium
LC 438 — Find All Anagrams in a StringMedium
LC 424 — Longest Repeating Character ReplacementMedium
LC 57 — Insert IntervalMedium

| LC 904 — Fruit Into Baskets | Medium | | | LC 159 — Longest Substring with At Most Two Distinct Characters | Medium | | | LC 209 — Minimum Size Subarray Sum | Medium | | | LC 340 — Longest Substring with At Most K Distinct Characters | Medium | | | LC 395 — Longest Substring with At Least K Repeating Characters | Medium | | | LC 435 — Non-overlapping Intervals | Medium | | | LC 452 — Minimum Number of Arrows to Burst Balloons | Medium | | | LC 713 — Subarray Product Less Than K | Medium | | | LC 930 — Binary Subarrays With Sum | Medium | | | LC 986 — Interval List Intersections | Medium | | | LC 992 — Subarrays with K Different Integers | Medium | | | LC 1208 — Get Equal Substrings Within Budget | Medium | | | LC 1248 — Count Number of Nice Subarrays | Medium | | | LC 1438 — Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Medium | | | LC 1493 — Longest Subarray of 1's After Deleting One Element | Medium | | | LC 1658 — Minimum Operations to Reduce X to Zero | Medium | | | LC 1695 — Maximum Erasure Value | Medium | | | LC 1838 — Frequency of the Most Frequent Element | Medium | | | LC 2024 — Maximize the Confusion of an Exam | Medium | | | CC — Maximum Unique Subarray Window (UNQEQ) | Medium | | | CC — Dynamic Window (DYNWIN) | Medium | | | CC — Interval Merging (INTMERGE) | Medium | | | CC — Substring Matching (SUBMATCH) | Medium | | | LC 76 — Minimum Window Substring | Hard | | | LC 239 — Sliding Window Maximum | Hard | | | LC 30 — Substring with Concatenation of All Words | Hard | | | LC 84 — Largest Rectangle in Histogram | Hard | | | LC 85 — Maximal Rectangle | Hard | | | LC 632 — Smallest Range Covering Elements from K Lists | Hard | | | LC 727 — Minimum Window Subsequence | Hard | | | LC 862 — Shortest Subarray with Sum at Least K | Hard | | | LC 1425 — Constrained Subsequence Sum | Hard | | | LC 1499 — Max Value of Equation | Hard | | | LC 1687 — Delivering Boxes from Storage to Ports | Hard | | | LC 1793 — Maximum Score of a Good Subarray | Hard | | | LC 2009 — Minimum Number of Operations to Make Array Continuous | Hard | | | LC 2444 — Count Subarrays With Fixed Bounds | Hard | | | CC — Advanced Sliding Window (ADVSLIDE) | Hard | | | CC — Complex Window Operations (COMPLEXWIN) | Hard | | | CC — Sliding Window Maximum (SLIDEMAX) | Hard | |

← Back to Home · © sparshjaswal

Last updated on