Arrays
Sliding Window Pattern
Master fixed and variable sliding window patterns to solve contiguous subarray and substring problems in O(N) linear time.
Last Updated: August 2, 2026
•
30 min read
1. Introduction
What is the Sliding Window Pattern?
The Sliding Window pattern is an optimization technique used to process contiguous sub-sequences (subarrays or substrings) of a data structure. Instead of re-evaluating the entire sub-segment from scratch as it moves, it incrementally updates the window state by adding the incoming element at the right boundary and subtracting the outgoing element at the left boundary.Why is it Important?
Brute-force solutions checking all contiguous subarrays of sizeK take O(N × K) or O(N²) time. Sliding window converts this to O(N) linear time by maintaining running window aggregates (sums, character counts, or frequencies).
Where is it Used?
2. Mental Model
Imagine a Magnifying Glass Window sliding across a strip of film.
To compute the sum of the new window, you don't add all 3 numbers again. You simply take the previous sum (7), subtract the number leaving the left side (1), and add the number entering the right side (3). This operation takes O(1) time regardless of how big the window K is!
3. Concept: The Two Sliding Window Types
1. Fixed-Size Sliding Window
Window sizeK remains constant throughout execution.
windowSum += arr[i] - arr[i - K].2. Variable-Size Sliding Window (Expand & Shrink)
Window size expands or shrinks dynamically based on a condition/constraint.right pointer to include new elements.left pointer to shrink window whenever constraint is violated.4. Visuals
Dynamic Window State Machine
Problem Classification Guide
| Problem Trigger Keyword | Window Type | Key State Tracking Structure |
|---|---|---|
| "Subarray of fixed size K" | Fixed | Single aggregate variable (windowSum) |
| "Longest subarray with condition X" | Variable | Frequency Map / Set |
| "Minimum window containing elements" | Variable | Frequency Count / Character Match Count |
5. Real-World Examples
6. Interview Perspective
How Interviewers Ask This Topic
Watch for problems containing words like "contiguous subarray", "substring", "maximum/minimum length", or "at most K distinct elements". Interviewers look to see if you can track window state inO(1) time per step.
Common Mistakes
Warning: 1. Resetting the Window Inside the Loop: Re-calculating sums or re-scanning window contents inside the loop turns an
O(N) sliding window back into an O(N²) brute force!> 2. Off-By-One Window Length: Current window length between indicesleftandrightisright - left + 1(inclusive of both ends).
7. Summary
O(1) step cost).right to fulfill requirement, shrink left when invariant is violated.O(N²) contiguous subarray problems into O(N) linear time solutions.8. Quiz
Question 1: What is the window length formula for indices left = 2 and right = 5 (inclusive)?
Answer:right - left + 1 = 5 - 2 + 1 = 4 elements (indices 2, 3, 4, 5).
Question 2: Why is the time complexity of a variable sliding window O(N) even though it has a nested while loop?
Answer: Because bothright and left pointers only move forward. right increments N times total, and left increments at most N times total. Total iterations across the entire execution = 2N = O(N).
Question 3: How do you maintain the state of a sliding window tracking "at most K distinct characters"?
Answer: Use a HashMap / Frequency Table. Expandright and increment character counts. If map.size() > K, shrink left and decrement character counts, removing characters when their count hits 0.