Sliding window and two pointer techniques are among the most frequently tested patterns in coding interviews. They convert O(n²) or O(n³) brute-force solutions into O(n) linear time, and appear in substring, subarray, and two-sequence problems across all major tech company interviews.
Two Pointer: Fundamentals
# Pattern 1: Converging pointers (sorted array, find pair)
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left, right]
elif s int:
"""LC 26: in-place, return new length"""
k = 0 # write pointer
for read in range(len(nums)):
if k == 0 or nums[read] != nums[k - 1]:
nums[k] = nums[read]
k += 1
return kPattern: Three Sum (Sort + Two Pointers)
def threeSum(nums: list[int]) -> list[list[int]]:
"""LC 15: all unique triplets summing to 0 — O(n²)"""
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # skip duplicate anchors
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 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 s < 0: left += 1
else: right -= 1
return result # Time O(n²), Space O(1)Fixed-Size Sliding Window
def max_sum_subarray_k(nums: list[int], k: int) -> int:
"""Maximum sum of any subarray of length k — O(n)"""
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # slide: add new, remove old
max_sum = max(max_sum, window_sum)
return max_sum
def find_all_anagrams(s: str, p: str) -> list[int]:
"""LC 438: All anagram start indices — O(n)"""
from collections import Counter
need = Counter(p)
have = Counter(s[:len(p)])
result = []
if have == need:
result.append(0)
for i in range(len(p), len(s)):
# add new char
have[s[i]] += 1
# remove old char
old = s[i - len(p)]
have[old] -= 1
if have[old] == 0:
del have[old]
if have == need:
result.append(i - len(p) + 1)
return resultVariable-Size Sliding Window (Expand/Shrink)
Template for "shortest/longest subarray satisfying condition":
def sliding_window_variable(nums, condition):
left = 0
result = float('inf') # or -inf for longest
window_state = initial_state
for right in range(len(nums)):
# EXPAND: add nums[right] to window
update(window_state, nums[right])
# SHRINK: move left until window is valid (for shortest)
# OR: while window is valid, try to shrink (for longest)
while condition(window_state):
result = min(result, right - left + 1)
remove(window_state, nums[left])
left += 1
return resultMinimum Size Subarray Sum
def minSubArrayLen(target: int, nums: list[int]) -> int:
"""LC 209: shortest subarray with sum >= target — O(n)"""
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0Longest Substring Without Repeating Characters
def lengthOfLongestSubstring(s: str) -> int:
"""LC 3 — O(n) with char index tracking"""
char_index = {} # char → last seen 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 past duplicate
char_index[ch] = right
max_len = max(max_len, right - left + 1)
return max_lenLongest Substring with At Most K Distinct Characters
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
"""LC 340 — O(n)"""
from collections import defaultdict
count = defaultdict(int)
left = 0
max_len = 0
for right, ch in enumerate(s):
count[ch] += 1
while len(count) > k:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
max_len = max(max_len, right - left + 1)
return max_lenPattern: Minimum Window Substring
def minWindow(s: str, t: str) -> str:
"""LC 76: smallest window in s containing all chars of t — O(n+m)"""
from collections import Counter
need = Counter(t)
missing = len(t) # total chars still needed
left = 0
best_left = best_right = -1
best_len = float('inf')
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
if missing == 0: # window contains all chars of t
# shrink from left
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
# left is now at tightest valid position
if right - left + 1 < best_len:
best_len = right - left + 1
best_left, best_right = left, right
# advance left to search for better windows
need[s[left]] += 1
missing += 1
left += 1
return s[best_left:best_right+1] if best_left != -1 else ''Pattern: Container With Most Water
def maxArea(height: list[int]) -> int:
"""LC 11: converging two pointers — O(n)"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
max_water = max(max_water, water)
# move the shorter wall inward (moving taller can't help)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_waterPattern: Trapping Rain Water
def trap(height: list[int]) -> int:
"""LC 42: two pointer O(n) time O(1) space"""
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] = left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
# Key insight: at any position, water trapped = min(max_left, max_right) - height
# Two-pointer approach: whichever side has smaller max determines water at current positionPattern: Sliding Window Maximum (Monotonic Deque)
from collections import deque
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
"""LC 239: max of each window — O(n)"""
dq = deque() # stores indices, decreasing values
result = []
for i, num 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]]) # front is always the max
return resultProblem Recognition Cheat Sheet
| Clue in Problem | Pattern |
|---|---|
| “sorted array”, “find pair/triplet summing to X” | Two pointers (converging) |
| “subarray/substring”, “sum/count/condition” | Sliding window (expand/shrink) |
| “at most K distinct”, “longest without repeating” | Variable-size window + hashmap |
| “fixed size window”, “max/min of all windows” | Fixed window or monotonic deque |
| “linked list cycle”, “find middle” | Fast/slow pointers |
| “remove duplicates in-place”, “partition” | Read/write pointers (same direction) |
Key Interview Tips
- When to shrink: For “shortest” problems, shrink when condition is satisfied. For “longest” problems, shrink when condition is violated. The template is the same — just swap the shrink trigger.
- Avoid comparison of Counter objects:
Counter == Counteris O(k) — track aformedcount instead (how many unique chars have required frequency) for O(1) per step. - Three-pointer problems: Dutch National Flag (3-way partition) uses three pointers — low, mid, high — to sort [0,1,2] in-place in a single pass.
- Two pointers in 2D: Problems like “search a sorted 2D matrix” — start from top-right corner: move left if value > target, move down if value < target. O(m+n).