The sliding window algorithm is a technique for solving problems that involve finding a subarray or substring that satisfies some condition within a larger array or string. Instead of recalculating from scratch for every possible subarray (which would be O(n²) or worse), a sliding window maintains a running result and expands or shrinks from one end as it moves through the data – bringing the time complexity down to O(n).
Think of it like a physical window frame you slide along a wall of tiles. You see a fixed number of tiles at once. As the window moves right by one, you add the new tile that enters the frame and remove the one that exits. You never need to count all visible tiles from scratch – just update the count. That is exactly what the algorithm does with data.
Fixed Window vs Variable Window
Fixed-size window: The window size k is given. You slide a window of exactly k elements through the array. Classic example: maximum sum of any k consecutive elements.
Variable-size window: The window expands and contracts based on a condition. Classic example: longest substring without repeating characters – you grow the window until a repeat appears, then shrink from the left until it is gone.
When to Use the Sliding Window Pattern
You are likely looking at a sliding window problem when you see:
- ‘Find the maximum/minimum/longest/shortest subarray or substring…’
- ‘…that satisfies condition X’ (a sum, a count of distinct elements, absence of repeats)
- ‘…of size k’ (fixed window) or ‘…in the entire array’ (variable window)
- The input is a linear data structure: array, string, or linked list
- Brute force would require nested loops – O(n²) or O(n³)
Pattern Reference Table
| Problem Type | Window Type | Time Complexity | Example Problem |
|---|---|---|---|
| Max sum subarray of size k | Fixed | O(n) | LeetCode 643 |
| Longest substring without repeating chars | Variable | O(n) | LeetCode 3 |
| Minimum window substring | Variable | O(n) | LeetCode 76 |
| Fruits into baskets (max 2 types) | Variable | O(n) | LeetCode 904 |
| Max consecutive ones (with k flips) | Variable | O(n) | LeetCode 1004 |
| Average of subarrays of size k | Fixed | O(n) | Educative / basic warmup |
| Permutation in string | Fixed | O(n) | LeetCode 567 |
Code Example 1: Maximum Sum Subarray of Size K (Fixed Window)
Problem: Given an integer array and a number k, find the maximum sum of any contiguous subarray of size k.
Brute force approach: for every starting index, sum the next k elements. That is O(n × k).
Sliding window approach: compute the first window sum, then for each subsequent position, add the new element entering the window and subtract the element leaving. O(n) total.
n = len(arr)
if n < k:
return -1
Compute sum of first window
window_sum = sum(arr[:k])
max_sum = window_sum
Slide the window forward
for i in range(k, n):
window_sum += arr[i] – arr[i – k] # add new, remove old
return max_sum
Example: arr = [2, 1, 5, 1, 3, 2], k = 3
Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6 → Answer: 9
Code Example 2: Longest Substring Without Repeating Characters (Variable Window)
Problem: Given a string, find the length of the longest substring that contains no duplicate characters.
This is a variable window problem. The window expands right as long as no character repeats. When a repeat is found, the left pointer moves forward until the repeat is resolved.
def length_of_longest_substring(s):
char_index = {} # stores last seen index of each char
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1 # shrink from left
char_index[s[right]] = right # update last seen
return max_len
Example: s = ‘abcabcbb’
‘abc’ → length 3, then ‘a’ repeats → window shifts → ‘bca’ → ‘cab’ → ‘abc’ → longest = 3
Brute Force vs Sliding Window: The Difference in Numbers
| Approach | Time Complexity | Space Complexity | For n=100,000 elements |
|---|---|---|---|
| Brute force (nested loops) | O(n²) | O(1) | ~10 billion operations |
| Sliding window | O(n) | O(1) to O(k) | ~100,000 operations |
| Speedup factor | – | – | ~100,000x faster |
The Two-Pointer Relationship
The sliding window pattern is a specific application of the two-pointer technique. The left pointer marks the start of the window and the right pointer marks the end. For fixed windows, both move at the same rate. For variable windows, the right pointer expands greedily and the left pointer catches up whenever the window condition is violated.
This mental model – left holds, right explores, left adjusts – covers the majority of sliding window interview problems once it clicks.
Common Interview Questions Using This Pattern
- LeetCode 3 – Longest Substring Without Repeating Characters (Medium)
- LeetCode 76 – Minimum Window Substring (Hard)
- LeetCode 121 – Best Time to Buy and Sell Stock (Easy – implicit fixed window)
- LeetCode 239 – Sliding Window Maximum (Hard – uses deque)
- LeetCode 424 – Longest Repeating Character Replacement (Medium)
- LeetCode 567 – Permutation in String (Medium)
- LeetCode 1004 – Max Consecutive Ones III (Medium)
Quick Recognition Checklist
- Is the input linear (array, string)?
- Am I looking for a subarray or substring?
- Is there a condition the window must satisfy?
- Would brute force require nested loops?
Four ‘yes’ answers = sliding window is almost certainly the intended approach. Start by defining what enters the window, what leaves the window, and what condition controls the size. The code almost writes itself from there.