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.
Transcript
You're in a twenty-five-minute screen, and the question is the longest substring with no repeated character. A huge fraction of array and string screens are really one of two patterns, and both of them turn the obvious O(n^2) double loop into a single O(n) pass that touches each element a constant number of times.
The trigger words are concrete. Contiguous subarray, substring, window of size k, longest or shortest range: sliding window. Sorted array, a pair that sums to a target, moving inward from both ends: two pointers. Either way, you never restart the scan, because the state you computed for one position gets reused for the next, and that's why the work is linear instead of quadratic.
Here's the mistake that reveals a weak candidate. They recompute the window from scratch on every step, which is the O(n*k) trap. Slide it instead, one step at a time. Add the entering element, subtract the leaving one, and each step costs O(1).
Here's the whole loop. Include the element at the right edge and update the running answer. When the constraint breaks, move the left edge right, record the best, advance the right edge, and go again. The left edge never moves back, so each element is touched at most twice.
Here's the classic: longest substring, no repeats. A dictionary remembers the most recent index of each character. This is the line interviewers watch: a repeat only moves start if it sits inside the current window, and leaving that check out is the bug. Length is right minus left, plus one.
Trace abba to see the guard earn its place. Index zero is A, and the window is just that. Index one, B. The window grows and best is two. Index two is B again, last seen at one, which is inside the window, so start jumps to two. Index three is A, last seen at zero, which is before start, so the guard leaves start at two and best stays two.
Now drop the guard. Start would jump back to one, and the window from one to three would be reported as three unique characters when it holds B twice.
Two pointers need sorted data. Take 1, 2, 4, 7, 11, 15, and a target of 13. Start at both ends. 1 plus 15 is 16, too big, so the high pointer steps in. 1 plus 11 is 12, too small, so the low one steps up. 2 plus 11 is 13, found.
Each step throws out exactly one candidate. When the sum was too small, the low element was finished, because the high element was the largest partner still available and even that wasn't enough. The mirror argument retires the high element when the sum is too large. One sweep. O(n) after the sort.
In the interview, name the pattern first. Then state the complexity out loud: O(n^2) brute force down to O(n) time, because you never recompute the window. The code and the abba trace are on fdeinterviews.com.
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).
The spine above is the window loop itself, with the constant-time update and the left edge that never moves backward marked as the two things the screen is actually testing.
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.
Trace "abba" to see the guard earn its place. At index 0, a: the window is [0, 0], best 1. Index 1, b: [0, 1], best 2. Index 2, b again: b was last seen at 1, inside the window, so start jumps to 2 and the window is [2, 2]. Index 3, a: a was last seen at 0, which is before start, so the guard leaves start at 2, the window is [2, 3], and best stays 2. Without the guard, start would jump to 1 and the window [1, 3] would be reported as three unique characters when it contains b twice.
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 reason a step can safely discard is the sort. If the sum is below the target, the low element cannot pair with anything, because the high element is the largest partner still available and even that was not enough, so the low element is finished. The mirror argument retires the high element when the sum is too large. 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.