Many brute-force solutions run in O(N²) or worse, which is unacceptable for large inputs. The Sliding Window technique is one of the most powerful ways to cut down unnecessary work and bring solutions down to O(N) or O(N log N).
If you’ve ever solved problems around subarrays, substrings, or continuous segments, chances are you’ve already touched sliding windows — maybe without realising it. This article will break down the concept, patterns, common pitfalls, and must-solve problems.
Table of Contents
What is Sliding Window?
At its core, Sliding Window is an optimization trick. Instead of recalculating results from scratch every time you move across an array or string, you “slide” a window and reuse previous computations by adding the new element and removing the old one.
Think of it like a magnifying glass scanning across text. You don’t throw away everything you saw before; you just update what changed.
Types of Sliding Windows
Fixed-size window
- The window length k is known in advance.
- You move the window one step at a time, maintaining the result efficiently.
- Best suited for problems like:
- Maximum/Minimum sum of subarray of size k
- Count distinct elements in every window of size k
- First negative number in each window
Example: Maximum sum of subarray of size k
def max_sum_subarray(nums, k):
curr_sum = sum(nums[:k])
max_sum = curr_sum
for i in range(k, len(nums)):
curr_sum += nums[i] - nums[i-k] # slide window
max_sum = max(max_sum, curr_sum)
return max_sum- Complexity: O(N)
Variable-size window
- The window length is not fixed; it grows or shrinks based on constraints.
- Managed with two pointers (left, right).
- Useful for problems like:
- Longest substring without repeating characters
- Smallest subarray with sum ≥ target
- Longest substring with at most k distinct characters
Example: Longest substring without repeating characters
def longest_unique_substring(s):
seen = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in seen and seen[s[right]] >= left:
left = seen[s[right]] + 1
seen[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
'''
seen[s[right]] >= left
since we never delete entries from the seen dictionary, that’s precisely why the condition
example
s = "abba"
↑
now left 2, right 2
but
s = "abba"
↑
now left =0, right 3
So we got 3 as the longest substring which is wrong
'''- Complexity: O(N)
Templates
Fixed Size
def fixed_window(nums, k):
n = len(nums)
window = nums[:k] # first window
print(window)
for right in range(k, n):
window.append(nums[right]) # add new element
del window[0] # Remove
print(window) # Windows
nums = [0,1,2,3,4,5,6,7,8,9]
fixed_window(nums,3)
'''
[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]
[5, 6, 7]
[6, 7, 8]
[7, 8, 9]
'''Variable-Size Window Template
def variable_window(arr, condition):
n = len(arr)
left = 0
result = 0
for right in range(n):
# Expand window
# (add arr[right] into current window data structure)
# While condition is violated → shrink from left
while not condition:
# (remove arr[left] from current window data structure)
left += 1
# Update result using current [left, right] window
result = _func(result, right - left + 1)
return result- Fixed-size window: Left and right move together to maintain constant window size.
- Variable-size window: Left and right move independently to expand or shrink based on conditions.
Frequency-Map Window Template
from collections import defaultdict
def sliding_window_freq(s, condition):
n = len(s)
freq = defaultdict(int)
left = 0
result = 0
for right in range(n):
freq[s[right]] += 1
# Shrink window while invalid
while not condition(freq):
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
# Process valid window
result = _func(result, right - left + 1)
return resultWhere Sliding Window Shines
Sliding window is a go-to strategy whenever you see:
- Contiguous subarrays or substrings
- “Longest/Shortest” substring/subarray problems
- Windowed frequency or counting problems
- Streaming/real-time data (where recalculating from scratch is impossible)
Classic Sliding Window Patterns
Fixed Window
- Maximum sum subarray of size k
- First negative number in each window
- Count distinct elements in each window
- Maximum of all subarrays of size k (using a Deque)
Variable Window
- Longest substring without repeating characters
- Longest substring with at most k distinct characters
- Smallest subarray with sum ≥ target
- Subarrays with product less than k
Advanced Variants
- Deque/Monotonic Queue → Sliding Window Maximum
- Heap / Two Heaps → Median of sliding window
- HashMap + Window → String anagram problems
- Prefix Sum + Window → Subarray sum constraints
Common Pitfalls
- Forgetting to shrink the window properly in variable-size cases → infinite loop.
- Off-by-one errors when updating indices.
- Failing to remove elements cleanly from HashMaps/counters.
- Updating the answer at the wrong time (during expansion vs contraction).
Practice
Maximum Average Subarray I
class Solution:
def findMaxAverage(self, nums: list[int], k: int) -> float:
# Step 1: Compute sum of first window
window_sum = sum(nums[:k]) #first result from first window
max_sum = window_sum
# Step 2: Slide the window
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # following results from following windows
max_sum = max(max_sum, window_sum)
# Step 3: Return max average
return max_sum / kContains Duplicate II
Way 1 Sliding Window + HashSet
class Solution:
def containsNearbyDuplicate(self, nums, k):
window = set()
for i, num in enumerate(nums):
if num in window:
return True
window.add(num)
if len(window) > k:
window.remove(nums[i - k])
return False
Way 2 : HashMap
class Solution:
def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
seen = {}
for i, num in enumerate(nums):
if num in seen and i - seen[num] <= k:
return True
seen[num] = i
return False
Way 3 Array
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
if k == 0 or len(nums) == len(set(nums)):
return False
for i in range(len(nums)):
if nums[i] in nums[i + 1 : i + k + 1]:
return True
return FalseLongest Substring Without Repeating Characters
Sliding Window with HashMap/Set
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set: # shrink until duplicate removed
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len- Time Complexity = O(n)
- Space Complexity = O(min(n, charset))
Time complexity O(n), not O(n²). That means even though the while loop is inside the for loop, it doesn’t restart from scratch for every iteration — instead, it just continues moving left forward.
Space Complexity, At first glance, we’re storing characters in a set or HashMap. In the worst case, we could store all characters of the string → O(n).
Optimized with HashMap (Skip Moves)
Instead of moving left one step at a time, we can jump directly using a dictionary that stores the last seen index of each character.
def lengthOfLongestSubstring(s: str) -> int:
char_index = {}
left = 0
max_len = 0
for right, ch in enumerate(s):
if ch in char_index and char_index[ch] >= left:
left = char_index[ch] + 1 # jump left pointer
char_index[ch] = right
max_len = max(max_len, right - left + 1)
return max_len
1 thought on “Mastering the Sliding Window Technique”