Two Pointers and Sliding Window Interview Patterns
Two pointers and sliding window are techniques that turn O(n²) brute-force solutions into O(n). They are among the most frequently tested patterns in coding interviews. This guide covers both techniques with clear templates and the problem types each solves.
Two Pointers: Opposite Direction
Start pointers at both ends of a sorted array and move them toward each other based on the comparison result.
# Two Sum II (sorted array, LeetCode 167):
def two_sum_sorted(nums, target):
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == target: return [l+1, r+1]
elif s < target: l += 1 # need larger sum, move left ptr right
else: r -= 1 # need smaller sum, move right ptr left
return []
# Valid Palindrome: same idea — compare from both ends, move inwardThree Sum (LeetCode 15)
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip duplicate
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
result.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1 # skip duplicates
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
elif s < 0: l += 1
else: r -= 1
return result
# Time O(n log n + n^2) = O(n^2), Space O(1)Two Pointers: Same Direction (Fast/Slow)
Two pointers move in the same direction at different speeds. Used for linked list cycle detection and in-place array manipulation.
# Remove Duplicates from Sorted Array (LeetCode 26):
def remove_duplicates(nums):
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Floyd cycle detection (linked list):
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 FalseSliding Window: Fixed Size
Maintain a window of exactly k elements, slide it one position at a time.
# Maximum Average Subarray of Length K (LeetCode 643):
def find_max_average(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] # add new, remove old
max_sum = max(max_sum, window_sum)
return max_sum / k
# Time O(n), Space O(1)Sliding Window: Variable Size
Expand right pointer to grow the window; shrink left pointer when the constraint is violated.
# Longest Substring Without Repeating Characters (LeetCode 3):
def length_of_longest_substring(s):
char_set = set()
l = max_len = 0
for r in range(len(s)):
while s[r] in char_set: # constraint violated: remove from left
char_set.remove(s[l])
l += 1
char_set.add(s[r])
max_len = max(max_len, r - l + 1)
return max_len
# Minimum Window Substring (LeetCode 76):
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
l = best_l = best_r = 0
for r, c in enumerate(s, 1):
if need[c] > 0: missing -= 1
need[c] -= 1
if missing == 0: # valid window found
while need[s[l]] < 0: # shrink from left
need[s[l]] += 1
l += 1
if best_r == 0 or r - l < best_r - best_l:
best_l, best_r = l, r
need[s[l]] += 1
missing += 1
l += 1
return s[best_l:best_r]Common Problem Patterns
| Problem | Pattern | LeetCode |
|---|---|---|
| Two sum on sorted array | Two pointers, opposite | 167, 15, 16, 18 |
| Container with most water | Two pointers, opposite | 11 |
| In-place array modification | Two pointers, same direction | 26, 27, 80, 283 |
| Linked list cycle | Fast/slow pointers | 141, 142, 287 |
| Max/min of fixed window | Sliding window, fixed | 643, 239 |
| Longest substring with constraint | Sliding window, variable | 3, 159, 340, 424 |
| Minimum window containing target | Sliding window, variable | 76, 567, 438 |
Variable Window Template
def sliding_window(s, k):
l = 0
state = {} # track window state (character counts, etc.)
result = 0
for r in range(len(s)):
# Expand: add s[r] to window state
state[s[r]] = state.get(s[r], 0) + 1
# Shrink: while constraint violated, remove s[l]
while len(state) > k: # example constraint: at most k distinct chars
state[s[l]] -= 1
if state[s[l]] == 0: del state[s[l]]
l += 1
# Update result (window is valid here)
result = max(result, r - l + 1)
return resultInterview Tips
- For any “longest/minimum subarray/substring” problem, try sliding window first
- The variable window shrink loop (while constraint violated) is the key — practice writing it from memory
- For three sum: sort first, fix one pointer, use two-pointer for the pair — this is the standard O(n²) approach
- Fast/slow pointer: the distance between them at cycle entry = distance from head to cycle entry (used in LeetCode 142)
- State your time complexity explicitly: “O(n) because each element enters and leaves the window at most once”
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use two pointers vs. a hash map for array problems?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use two pointers when: the array is sorted (or can be sorted), you need O(1) space, the problem asks for pairs/triplets summing to a target. Two pointers give O(n) time after O(n log n) sort. Use a hash map when: the array is unsorted and sorting would destroy information (e.g., "find pair with difference k"), you need to remember the index of each element (Two Sum classic), or you need O(n) time with O(n) space. Rule: if the problem gives a sorted array and asks for pairs/triplets, two pointers. If unsorted and you need exact positions, hash map. For Three Sum, sort first then two pointers – O(n^2) total which is optimal.” }
},
{
“@type”: “Question”,
“name”: “What is the variable sliding window pattern and how do you apply it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Variable sliding window: expand the right pointer to grow the window, shrink the left pointer when a constraint is violated. Template: initialize l=0, state={}. For each r: add s[r] to state. While state violates constraint: remove s[l] from state, l++. Update result with current window [l, r]. This works because: expanding right is always productive, shrinking left only when necessary. Each element is added and removed at most once: O(n) total. Constraint examples: "at most k distinct characters" (len(state) > k triggers shrink), "no repeating character" (s[r] in char_set triggers shrink), "contains all chars of t" (missing > 0 prevents result update until satisfied). Minimum Window Substring (LC 76) uses the inverted pattern: shrink while the window is valid to minimize size.” }
},
{
“@type”: “Question”,
“name”: “How does Floyd cycle detection (fast/slow pointers) find the cycle start?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Phase 1: detect a cycle. fast moves 2 steps, slow moves 1 step. If they meet, a cycle exists. Phase 2: find the cycle entry. Key mathematical insight: when fast and slow meet inside the cycle, the distance from head to cycle entry equals the distance from the meeting point to cycle entry (going forward in cycle direction). Proof: let F = distance from head to cycle entry, C = cycle length, h = distance from cycle entry to meeting point. Slow traveled F+h, fast traveled F+h+n*C (at least one extra loop). Fast = 2*slow: F+h+n*C = 2(F+h), so F = n*C – h = distance from meeting point to cycle entry. Algorithm: reset slow to head; move both slow and fast one step at a time; they meet at the cycle entry. Used in LeetCode 142 (Linked List Cycle II) and 287 (Find Duplicate Number).” }
}
]
}