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).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you recognize when to use the sliding window technique?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use sliding window when the problem asks about a contiguous subarray or substring and involves finding a min/max length, count, or sum satisfying a condition. Key signals: “longest/shortest subarray”, “minimum window”, “at most K distinct characters”, “subarray sum equals target”. The window expands by moving the right pointer and contracts by moving the left pointer. Fixed-size windows apply when K is given explicitly; variable-size windows use a condition to decide when to shrink. If elements are non-negative, you can use two pointers; if negative numbers appear, you may need prefix sums or deques instead.”
}
},
{
“@type”: “Question”,
“name”: “What is the time complexity advantage of sliding window over brute force?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Brute force for subarray problems is O(nu00b2) or O(nu00b3): enumerate all start/end pairs and compute the condition. Sliding window reduces this to O(n) because each element is added to the window exactly once (right pointer moves right) and removed at most once (left pointer moves right) u2014 total pointer movements are at most 2n. For the “minimum window substring” problem, brute force is O(nu00b2 u00d7 m) to check each substring; sliding window with a character count is O(n + m). The key invariant: both pointers only move forward, so you never re-examine an element.”
}
},
{
“@type”: “Question”,
“name”: “How does the monotonic deque solve the sliding window maximum problem in O(n)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The deque maintains indices of elements in decreasing order of value. When moving the window right: (1) remove indices from the front that are outside the window boundary; (2) remove indices from the back whose values are less than the new element (they can never be the maximum while the new element is in the window); (3) append the new index to the back; (4) the front of the deque is always the index of the current window’s maximum. Each index is added once and removed once u2014 O(n) total. This generalizes to any “sliding window min/max” problem and to problems requiring the next greater element.”
}
}
]
}