Sliding window and two pointers are among the most powerful patterns for array and string problems. Recognizing when to apply them turns an O(n²) brute force into an O(n) solution. This guide teaches both patterns with template code you can adapt to any problem.
Two Pointers Pattern
When to use: sorted arrays, finding pairs/triplets, in-place operations
from typing import List, Optional
# Classic: two-sum in sorted array
def two_sum_sorted(nums: List[int], target: int) -> List[int]:
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
elif total List[List[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # Skip duplicates for i
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
elif total int:
left, right = 0, len(heights) - 1
best = 0
while left < right:
area = min(heights[left], heights[right]) * (right - left)
best = max(best, area)
if heights[left] int:
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Trapping rainwater: use two-pointer O(n) time, O(1) space
def trap(heights: List[int]) -> int:
left, right = 0, len(heights) - 1
left_max = right_max = 0
water = 0
while left < right:
if heights[left] <= heights[right]:
left_max = max(left_max, heights[left])
water += left_max - heights[left]
left += 1
else:
right_max = max(right_max, heights[right])
water += right_max - heights[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
Fixed-Size Sliding Window
# Template: when window size k is given
def fixed_window_template(arr: List, k: int):
window_state = ... # Initialize with first k elements
best = window_state
for right in range(k, len(arr)):
# Add arr[right] to window
# Remove arr[right - k] from window
best = max(best, window_state) # or min, or check condition
return best
# Max sum of k consecutive elements
def max_sum_k(nums: List[int], k: int) -> int:
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # Slide: add right, remove left
best = max(best, window_sum)
return best
# Average of subarrays of size k
def avg_subarrays(nums: List[int], k: int) -> List[float]:
window_sum = sum(nums[:k])
result = [window_sum / k]
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
result.append(window_sum / k)
return result
# Sliding window maximum (deque maintains max efficiently)
from collections import deque
def sliding_window_max(nums: List[int], k: int) -> List[int]:
"""O(n) using monotonic deque. deque[0] is always the max."""
dq = deque() # Stores indices; front = index of max element
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order: remove smaller elements from back
while dq and nums[dq[-1]] = k - 1:
result.append(nums[dq[0]])
return result
print(sliding_window_max([1,3,-1,-3,5,3,6,7], 3)) # [3,3,5,5,6,7]
Dynamic Sliding Window
# Template: window size varies; expand right, shrink left when invalid
def dynamic_window_template(s: str, condition) -> int:
left = 0
best = 0
window = {} # Or a counter, or a set
for right in range(len(s)):
# Expand: add s[right] to window
window[s[right]] = window.get(s[right], 0) + 1
while not condition(window): # Window invalid: shrink
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
best = max(best, right - left + 1) # Window is valid here
return best
# Longest substring without repeating characters
def length_of_longest_substring(s: str) -> int:
seen = {} # char -> last seen index
left = best = 0
for right, c in enumerate(s):
if c in seen and seen[c] >= left:
left = seen[c] + 1 # Jump left past duplicate
seen[c] = right
best = max(best, right - left + 1)
return best
# Minimum window substring: smallest window in s containing all chars of t
from collections import Counter
def min_window(s: str, t: str) -> str:
if not t: return ""
need = Counter(t)
missing = len(t) # How many chars from t not yet in window
best_start = best_end = None
left = 0
for right, c in enumerate(s):
if need.get(c, 0) > 0:
missing -= 1
need[c] = need.get(c, 0) - 1
if missing == 0: # Window contains all of t
# Shrink from left while valid
while need.get(s[left], 0) < 0:
need[s[left]] = need.get(s[left], 0) + 1
left += 1
# Update best
if best_end is None or right - left int:
count = Counter()
left = best = 0
for right, c in enumerate(s):
count[c] += 1
while len(count) > k: # Too many distinct chars: shrink
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1)
return best
# Subarray product less than k
def num_subarrays_product_less_than_k(nums: List[int], k: int) -> int:
if k = k:
product //= nums[left]
left += 1
count += right - left + 1 # All subarrays ending at right
return count
Pattern Recognition Cheatsheet
| Problem Type | Pattern | Key Signal |
|---|---|---|
| Two values summing to target in sorted array | Two pointers | Sorted + pair search |
| Triplets/quadruplets summing to target | Sort + two pointers inside loop | Multiple elements, reduce to pair |
| Merge two sorted arrays/lists | Two pointers | Both inputs sorted |
| In-place array modification | Slow/fast pointers | Remove/move elements without extra space |
| Max/min sum of k elements | Fixed window | Exact window size given |
| Longest substring with constraint | Dynamic window | Expand/shrink based on validity |
| All subarrays satisfying condition | Dynamic window + count | Count += right – left + 1 per valid window |
| Sliding window maximum/minimum | Monotonic deque | Max/min of each window needed |
Frequently Asked Questions
When should you use the sliding window technique?
Use sliding window when the problem involves a contiguous subarray or substring and you need to find an optimal length, sum, or count within a window constraint. Signals: "subarray with sum equal to k", "longest substring without repeating characters", "minimum window containing all characters". Fixed-size windows use two pointers advancing together; variable-size windows expand the right pointer and shrink the left when the constraint is violated.
What is the two-pointer technique and when does it apply?
Two pointers maintains two indices that move through the data, typically converging from both ends or moving in the same direction. Apply when: finding pairs/triplets that sum to a target in a sorted array (opposite-direction pointers), merging two sorted arrays, removing duplicates in-place, or partitioning arrays. The key prerequisite for opposite-direction two pointers is a sorted array or monotonic property that lets you decide which pointer to move.
What is the time complexity of the sliding window approach vs brute force?
Brute force over all subarrays is O(n^2) — for each start, expand to find the best end. Sliding window reduces this to O(n) because each element is added to the window at most once and removed at most once, giving O(2n) = O(n) total operations. This transforms many quadratic problems to linear, which is the core insight behind most sliding window optimizations.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use the sliding window technique?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use sliding window when the problem involves a contiguous subarray or substring and you need to find an optimal length, sum, or count within a window constraint. Signals: “subarray with sum equal to k”, “longest substring without repeating characters”, “minimum window containing all characters”. Fixed-size windows use two pointers advancing together; variable-size windows expand the right pointer and shrink the left when the constraint is violated.”
}
},
{
“@type”: “Question”,
“name”: “What is the two-pointer technique and when does it apply?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Two pointers maintains two indices that move through the data, typically converging from both ends or moving in the same direction. Apply when: finding pairs/triplets that sum to a target in a sorted array (opposite-direction pointers), merging two sorted arrays, removing duplicates in-place, or partitioning arrays. The key prerequisite for opposite-direction two pointers is a sorted array or monotonic property that lets you decide which pointer to move.”
}
},
{
“@type”: “Question”,
“name”: “What is the time complexity of the sliding window approach vs brute force?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Brute force over all subarrays is O(n^2) — for each start, expand to find the best end. Sliding window reduces this to O(n) because each element is added to the window at most once and removed at most once, giving O(2n) = O(n) total operations. This transforms many quadratic problems to linear, which is the core insight behind most sliding window optimizations.”
}
}
]
}