When to use. Sorted array, opposite ends, or a list you can walk at two speeds.
Complexity. Time O(n) after any required sort. Space O(1) extra.
Who gets asked. Interns get sorted pair-sum. Mid-level gets in-place partition and cycle detection.
Prereq. Arrays & strings; linked lists for the fast/slow variant.
Two Pointers
Two indices walk a sequence so you do not nest two loops. After a sort — or on a list with a slow and a fast walker — pair search becomes linear.
The idea
The intern version: a sorted array, left at 0, right at n−1. Move the pointer that makes the pair-sum closer to the target. Each step discards an index forever, so the loop is O(n) after the sort.
The list version: slow advances one node, fast advances two. If they meet, there is a cycle. If fast hits null, there is not. Same idea — two cursors, one invariant.
Do not use two pointers on an unsorted array when order matters unless you are partitioning in place (Dutch-flag style). If you need original indices, keep a map or sort index pairs.
Worked example
Pair with target sum (sorted)
You have a sorted number list and a target. Return whether any two distinct positions add to the target. Example: [2, 3, 6, 9] and 9 → true (3+6).
left = 2, right = 9, sum = 11 > 9 → move right leftward.
left = 2, right = 6, sum = 8 < 9 → move left rightward.
left = 3, right = 6, sum = 9 → done. Each index moved at most once.
function hasPairSum(sorted, target) {
let left = 0;
let right = sorted.length - 1;
while (left < right) {
const sum = sorted[left] + sorted[right];
if (sum === target) return true;
if (sum < target) left += 1;
else right -= 1;
}
return false;
}
Time O(n) after the array is sorted. Space O(1).
Practice shapes
Original prompts — same family as interview questions, not copied statements.
Opposite-end palindrome
A string of letters. Ignore case. Are the letters a palindrome if you only compare from both ends inward?
Aim: O(n) time, O(1) space
Remove duplicates in place
Sorted numbers. Compact unique values to the front and return the new length. Extra array not allowed.
Aim: O(n) time, O(1) space
Cycle in a chain
Each node points to at most one next node. Detect whether following next forever loops. You may not store every visited id if you can use two speeds.