Two Pointers and Sliding Window
Two index variables walk an array so a nested loop becomes a single pass. Learn when each pattern applies, with three worked problems and the mistakes interviewers look for.
Two pointers and sliding window both replace an O(n^2) nested loop with a single O(n) pass by moving two indexes in a controlled way. Use two pointers on sorted data or from both ends, and a sliding window when the answer is a contiguous subarray or substring. Interviewers expect why it is O(n): the left pointer only moves forward.
Two pointers and sliding window both replace an O(n²) nested loop with a single O(n) pass by moving indexes in a controlled way. Use two pointers when the data is sorted or you work from both ends. Use a sliding window when the answer is a contiguous stretch of the array.
- Two pointers and sliding window turn an O(n^2) nested loop into an O(n) pass, because each pointer moves at most n times across the whole run.
- For sorted pair sum, two pointers start at both ends: move the left one right if the sum is too small and the right one left if it is too large.
- A flexible sliding window expands the right edge every step and moves the left edge only when the window breaks the condition, so a while loop inside a for loop is still O(n).
- In the longest substring without repeats problem, the check seen[ch] >= left is needed, or a character outside the window, as in abba, pulls the left edge backward.
- The minimum-length subarray with sum at least a target works as a sliding window only when all numbers are positive; with negatives, use prefix sums with a hash map.
01The idea in one minute
Take a problem like "find two numbers in a list that add up to 10". The brute force checks every pair, which is n times n comparisons. If the list is sorted you can do much better, because the order tells you which way to move.
Put one index at the start and one at the end. If the two values add to less than the target, the left value is too small, so move the left index right. If they add to more, the right value is too big, so move the right index left. Every step throws away at least one candidate for good. That is the whole trick: each pointer moves at most n times, so the total work is O(n).
A sliding window is the same idea with a different shape. Both pointers move in the same direction and the region between them is the "window". You grow the window from the right and shrink it from the left.
02Two pointers from both ends
Here is the sorted pair-sum problem.
def pair_sum(a, target):
i, j = 0, len(a) - 1
while i < j:
s = a[i] + a[j]
if s == target:
return (i, j)
if s < target:
i += 1
else:
j -= 1
return None
print(pair_sum([1, 3, 4, 6, 8, 11], 10)) # (2, 3)The output is (2, 3) because 4 + 6 = 10. The loop stops when the pointers meet, so no pair is checked twice.
The same shape solves checking whether a string is a palindrome, merging two sorted arrays, reversing in place, and the three-sum problem (fix one element, then run the pair search on the rest). Three-sum costs O(n²) in total, which matches the best known bounds for it up to small factors (the 3SUM conjecture says no truly subquadratic algorithm exists).
03A fixed window, then a flexible one
A fixed window is the easy version. To find the best sum of any 3 consecutive numbers, keep a running sum. Add the new element at the right, subtract the one that fell off the left. You never re-add the whole window.
A flexible window is where interviews live. The rule is: expand the right edge every step, and move the left edge only when the window breaks the condition. The left edge never goes backward, so it moves at most n times in total, and the whole thing is O(n) even though there is a loop inside a loop.
That last point confuses people. A while inside a for does not automatically mean O(n²). Count how many times the inner loop can run across the whole outer loop. Here it is at most n, because the left pointer only advances.
04Worked example: longest substring without repeats
Given a string, find the length of the longest stretch with no repeated character.
def longest_unique(s):
seen = {} # char -> last index
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return best
print(longest_unique("abcabcbb")) # 3 (abc)
print(longest_unique("pwwkew")) # 3 (wke)The check seen[ch] >= left is the part people forget. A character may have been seen before but sit to the left of the window, which means it no longer counts as a repeat. Without that check, "abba" gives the wrong answer: when the second a arrives, the old a is already outside the window and must not pull the left edge backward.
05Worked example: smallest subarray with sum at least a target
Given positive numbers and a target, find the shortest contiguous piece whose sum is at least the target.
def min_len(nums, target):
left = total = 0
best = float('inf')
for right, x in enumerate(nums):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float('inf') else best
print(min_len([2, 3, 1, 2, 4, 3], 7)) # 2 (4 + 3)This only works because every number is positive. Adding an element can only raise the sum and removing one can only lower it, so shrinking from the left is always safe. If negatives are allowed the window is no longer monotonic and you need a different tool, usually prefix sums with a hash map or a monotonic deque.
06How to recognise which one to use
Reach for two pointers when the array is sorted (or can be sorted without breaking the question), when you compare elements from opposite ends, or when you partition in place, like moving zeros to the end.
Reach for a sliding window when the question says "subarray" or "substring", asks for the longest, shortest or count of a contiguous range, and has a condition you can check incrementally with a counter, a sum or a hash map.
If the elements are not sorted and you need non-adjacent pairs, neither pattern fits. A hash set or hash map is the usual answer there. Sorting first costs O(n log n) and loses the original indexes, which matters when the question wants positions.
07Common interview questions
Q: Why is a sliding window O(n) when it has a loop inside a loop?
A: The left pointer only ever moves forward, so across the entire run it advances at most n times. Total work is n for the right pointer plus n for the left.
Q: Does two pointers need a sorted array?
A: For the opposite-ends version that depends on order, yes. For same-direction uses such as removing duplicates in place or the slow and fast pointer, no.
Q: What goes wrong with negative numbers in the subarray-sum window?
A: The sum no longer moves in one direction as the window grows, so you cannot decide when to shrink. Use prefix sums and a hash map instead.
Q: How do you find the longest substring with at most k distinct characters?
A: Keep a count map for the window. Expand right, and while the map holds more than k keys, shrink from the left and decrement counts, deleting keys that reach zero.
Q: What is the space cost?
A: Pair-sum uses O(1). The substring problems use O(k) or O(alphabet size) for the map.