Sliding Window and Two Pointers
A huge fraction of array and string screens are really one of two patterns. Two pointers walk a sorted structure from both ends or at two speeds; the sliding window keeps a running answer over a contiguous range and slides instead of recomputing. Both turn an obvious O(n^2) double loop into a single O(n) pass, and recognizing which one applies is most of the battle in a 25-minute screen.
TL;DR: When a problem asks about a contiguous subarray or substring, reach for a sliding window: expand the right edge to include elements, shrink the left edge when a constraint breaks, and keep a running answer so each element is touched at most twice. When the data is sorted (or you want pairs from both ends), two pointers collapse the same O(n^2) scan into O(n).
When each one fires
The trigger words are concrete. "Contiguous subarray", "substring", "window of size k", "longest/shortest range satisfying X" mean sliding window. "Sorted array", "pair that sums to target", "move inward from both ends", or "fast and slow pointer" mean two pointers. The shared idea is that you never restart the scan: state computed for one position is reused for the next, so the work is linear instead of quadratic.
The mistake that reveals a weak candidate is recomputing the window from scratch on every step. That is the O(n*k) trap. The whole point is to add the entering element and subtract the leaving one in O(1).
Sliding window: longest substring without repeats
def longest_unique(s: str) -> int:
last = {} # char -> most recent index
start = 0 # left edge of the window
best = 0
for i, ch in enumerate(s):
# if ch was seen inside the current window, jump start past it
if ch in last and last[ch] >= start:
start = last[ch] + 1
last[ch] = i
best = max(best, i - start + 1)
return best
assert longest_unique("abcabcbb") == 3 # "abc"
assert longest_unique("bbbbb") == 1
assert longest_unique("") == 0
The left edge only ever moves right, so each character is visited a constant number of times: O(n) time, O(k) space for the alphabet. The bug interviewers watch for is last[ch] >= start. Without that guard, a repeat that lives outside the current window wrongly drags start backward.
Two pointers: pair sum in a sorted array
def has_pair_sum(nums: list[int], target: int) -> bool:
lo, hi = 0, len(nums) - 1 # nums is sorted ascending
while lo < hi:
cur = nums[lo] + nums[hi]
if cur == target:
return True
if cur < target:
lo += 1 # need a larger sum
else:
hi -= 1 # need a smaller sum
return False
assert has_pair_sum([1, 2, 4, 7, 11, 15], 13) is True # 2 + 11
assert has_pair_sum([1, 2, 4, 7], 100) is False
Each step discards exactly one candidate, so the whole array is swept once: O(n) after the sort. The fast/slow variant of two pointers (one moves one step, the other two) is how you detect a cycle in a linked list or find a midpoint in a single pass.
Common pitfalls
- Recomputing instead of sliding. Summing the window every step is O(n*k). Maintain the running value incrementally.
- Off-by-one on the window size. The length of an inclusive window is
right - left + 1, notright - left. - Forgetting the in-window check. For "no repeats" style problems, an index seen long ago must not move the left edge.
- Two pointers on unsorted data. The technique assumes order. If the input is not sorted and you cannot sort it, a hash set or sliding window is usually the real answer.
Key takeaways
- Contiguous-range questions are sliding-window questions: grow right, shrink left, keep a running answer, touch each element O(1) times.
- Sorted-array or pair-from-both-ends questions are two-pointer questions: each step eliminates one candidate for an O(n) sweep.
- The signal of competence is incremental update (add the entering element, remove the leaving one), never recomputing the window.
- State the complexity out loud: most of these go from O(n^2) brute force to O(n) time and O(1) or O(k) space.