Two Pointers and Sliding Window Interview Patterns
Two-pointer techniques transform O(n²) brute-force solutions into O(n) elegant ones. They are among the highest-ROI patterns to master for coding interviews. Sliding window is a specialized two-pointer pattern for subarray/substring problems.
Pattern 1: Opposite-Direction Two Pointers
Use when array is sorted and you need pairs summing to a target, or need to close in from both ends.
# Two Sum II (sorted array)
def two_sum_sorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target: return [lo+1, hi+1]
elif s < target: lo += 1
else: hi -= 1
return []
# Container With Most Water
def max_area(height):
lo, hi = 0, len(height) - 1
res = 0
while lo < hi:
res = max(res, min(height[lo], height[hi]) * (hi - lo))
if height[lo] 0 and nums[i] == nums[i-1]: continue # skip duplicates
lo, hi = i+1, len(nums)-1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0: lo += 1
else: hi -= 1
return result
Pattern 2: Same-Direction Two Pointers (Fast/Slow)
Use for linked list cycle detection, finding middle, removing duplicates in-place.
# Linked list cycle detection (Floyd's algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Remove duplicates from sorted array in-place
def remove_duplicates(nums):
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
nums[k] = nums[i]
k += 1
return k
# Move zeroes to end
def move_zeroes(nums):
k = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[k], nums[i] = nums[i], nums[k]
k += 1
Pattern 3: Fixed-Size Sliding Window
Maintain a window of exactly k elements, slide it across the array.
# Maximum sum subarray of size k
def max_sum_subarray(nums, k):
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i-k]
max_sum = max(max_sum, window_sum)
return max_sum
Pattern 4: Variable-Size Sliding Window
Expand right pointer to include, shrink left when constraint violated. Classic for substring problems.
# Longest substring without repeating characters
def length_of_longest_substring(s):
char_idx = {}
max_len = left = 0
for right, ch in enumerate(s):
if ch in char_idx and char_idx[ch] >= left:
left = char_idx[ch] + 1
char_idx[ch] = right
max_len = max(max_len, right - left + 1)
return max_len
# Minimum window substring
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
best = ""
left = 0
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if not best or right - left + 1 k:
l_ch = s[left]
count[l_ch] -= 1
if count[l_ch] == 0:
del count[l_ch]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Classic Two Pointer / Sliding Window Problems
| Problem | Pattern | Time |
|---|---|---|
| Two Sum II | Opposite-direction | O(n) |
| 3Sum | Sort + opposite-direction | O(n²) |
| Container With Most Water | Opposite-direction | O(n) |
| Linked List Cycle | Fast/slow pointers | O(n) |
| Longest Substring No Repeat | Variable sliding window | O(n) |
| Minimum Window Substring | Variable sliding window | O(n) |
| Sliding Window Maximum | Monotonic deque | O(n) |
| Trapping Rain Water | Opposite-direction or stack | O(n) |
Decision Framework
- Sorted array + pair/triplet sum → opposite-direction two pointers
- Linked list cycle / middle / n-th from end → fast/slow pointers
- Subarray/substring with fixed size k → fixed sliding window
- Subarray/substring with constraint (at most k distinct, sum ≤ target) → variable sliding window
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use the sliding window technique vs two pointers?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use two pointers (opposite direction) when the array is sorted and you are looking for pairs or triplets satisfying a condition—you can close in from both ends. Use sliding window when you need a contiguous subarray or substring satisfying a constraint (length, sum, number of distinct characters). Fixed sliding window: window size is given. Variable sliding window: expand right, shrink left when constraint is violated.” }
},
{
“@type”: “Question”,
“name”: “How does Floyd's cycle detection algorithm (fast/slow pointers) work?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Floyd's algorithm uses two pointers moving at different speeds: slow advances one node per step, fast advances two. If a cycle exists, fast will eventually lap slow and they will meet inside the cycle. After meeting, reset one pointer to head and advance both one step at a time—they meet at the cycle entry point. Time O(n), space O(1)—far better than storing visited nodes in a hash set.” }
},
{
“@type”: “Question”,
“name”: “What is the minimum window substring problem and how do you solve it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Given strings s and t, find the smallest contiguous substring of s containing all characters of t. Approach: use a frequency counter for t and a sliding window. Expand right pointer to include characters; when all t characters are covered (missing==0), try shrinking the left pointer while maintaining coverage. Track the minimum valid window found. Time O(n), space O(|t|). The key insight: only advance left when the window still satisfies the constraint.” }
}
]
}