Sliding Window Algorithm: The Pattern That Unlocks a Whole Problem Category
There is a class of array and string problems where the naive approach leads to inefficient $O(n^2)$ time complexity. The sliding window algorithm exists specifically to solve these problems in $O(n)$ time. Once you recognize the pattern of maintaining a sub-segment of data as you iterate, a whole category of technical interview and real-world problems becomes significantly easier to solve.
The sliding window algorithm maintains a ‘window’ – a contiguous subset of an array or string – and slides it across the data structure while tracking some value (a sum, a count, a frequency map). Instead of recomputing from scratch each time the window moves, it updates incrementally. That is the entire idea, and it is more powerful than it sounds.
The Problem It Solves: Brute Force vs. Sliding Window
Take this classic problem: find the maximum sum of any contiguous subarray of size K in an array of n integers.
Brute force approach: for each starting position i from 0 to n-K, compute the sum of elements from i to i+K-1. That is O(n·K) – for large arrays with large K, this becomes very slow.
Sliding window approach: compute the sum of the first K elements once. Then for each step, subtract the element leaving the window on the left and add the element entering on the right. Each step is O(1). Total: O(n). Same result, dramatically less work.
Fixed Window vs. Variable Window
| Property | Fixed Window | Variable Window |
|---|---|---|
| Window size | Constant (K specified in problem) | Shrinks/expands based on a condition |
| When to use | “Find max/min of subarray of size K” | “Longest substring with at most K distinct chars” |
| Left pointer movement | Moves in lockstep with right (always K apart) | Moves only when a constraint is violated |
| Right pointer movement | Always moves one step at a time | Always moves one step at a time |
| Typical complexity | O(n) | O(n) amortised |
| Examples | Max sum subarray size K, sliding average | Longest substring without repeating chars, min window substring |
How a Fixed Sliding Window Works: Step by Step
Problem: find the maximum sum of any subarray of size 3 in [2, 1, 5, 1, 3, 2].
- Step 1 – Initialise: compute the sum of the first window [2, 1, 5] = 8. Set maxSum = 8.
- Step 2 – Slide: move the window right. Subtract the leftmost element (2), add the new rightmost element (1). New sum = 8 – 2 + 1 = 7. maxSum stays 8.
- Step 3 – Continue: subtract 1, add 3. Sum = 7 – 1 + 3 = 9. maxSum = 9.
- Step 4 – Continue: subtract 5, add 2. Sum = 9 – 5 + 2 = 6. maxSum stays 9.
- Step 5 – End of array. Return maxSum = 9.
Each step was a single subtraction and addition. No inner loop. No recomputation.
How a Variable Window Works
Problem: find the length of the longest substring without repeating characters in ‘abcabcbb’.
- Use a left pointer (L) and right pointer (R), both starting at 0. Use a set to track characters in the current window.
- Move R right, adding characters to the set. While a character at R already exists in the set (duplicate found), move L right, removing the character at L from the set until no duplicate exists.
- At each step, record the current window size (R – L + 1) as a candidate for the maximum.
- Result: the maximum recorded window size = 3 (for ‘abc’).
Classic Problems Solved by Sliding Window
| Problem | Window Type | Key Insight | Difficulty |
|---|---|---|---|
| Maximum sum subarray of size K | Fixed | Subtract left, add right each step | Easy |
| Longest substring without repeating chars | Variable | Expand right, shrink left on duplicate | Medium |
| Minimum window substring (contains all of T) | Variable | Track char frequency map, shrink when valid | Hard |
| Fruits into baskets (max 2 types) | Variable | At most 2 distinct values in window | Medium |
| Longest subarray with sum ≤ K | Variable | Shrink window when sum exceeds K | Medium |
| Maximum vowels in substring of length K | Fixed | Count vowels entering/leaving window | Easy |
| Sliding window maximum (deque) | Fixed | Monotonic deque tracks window max in O(1) | Hard |
| Count occurrences of anagrams | Fixed | Frequency map comparison at each window | Medium |
Pseudocode: Max Sum Subarray of Size K
The following logic walkthrough shows the fixed window pattern in plain pseudocode:
- function maxSumSubarray(arr, k):
- windowSum = sum of arr[0..k-1] // initialise first window
- maxSum = windowSum
- for i from k to len(arr) – 1:
- windowSum += arr[i] // add new element entering window
- windowSum -= arr[i – k] // remove element leaving window
- maxSum = max(maxSum, windowSum)
- return maxSum
Time complexity: O(n). Space complexity: O(1). This is the template for every fixed window problem.
Time and Space Complexity Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute force (nested loops) | O(n·K) or O(n²) | O(1) | Recomputes each subarray from scratch |
| Fixed sliding window | O(n) | O(1) | Single pass, constant extra space |
| Variable sliding window | O(n) amortised | O(K) for frequency map | Each element enters/exits window once |
| Sliding window with deque | O(n) | O(K) | Monotonic deque for max/min queries |
When NOT to Use Sliding Window
- When the subarray or substring does not need to be contiguous – sliding window only works on contiguous windows
- When you need non-adjacent elements or are working with a 2D matrix (different techniques apply)
- When the constraint involves global properties that cannot be checked incrementally
- When the array is not sorted and the problem involves subarrays where order of elements matters non-locally
Interview Tips for This Pattern
- Recognise the trigger words: ‘contiguous subarray’, ‘substring’, ‘window of size K’, ‘longest/shortest subarray satisfying X’
- Always clarify: fixed K or variable constraint? That determines which template to use
- Start by coding the brute force, then explain why sliding window reduces it to O(n) – interviewers want to see you understand the optimisation
- For variable windows, think about: what condition expands the window (R moves right) and what condition forces a shrink (L moves right)
- Common data structures alongside the window: HashSet for duplicates, HashMap for frequency counts, deque for max/min
The sliding window pattern does not just save time complexity – it trains a mode of thinking about problems as continuous processes rather than repeated computations. Once it clicks, you start seeing it in problems that did not initially look like window problems. That is when it becomes genuinely useful.
