Two-Pointer Technique

The two-pointer technique is one of the highest-yield patterns for array and string interviews: it turns many O(n²) brute-force scans into a single O(n) pass with O(1) extra space. Whenever you catch yourself writing a nested loop over the same array, ask "can two pointers replace the inner loop?"

The core idea

Keep two indices and move them under a rule instead of re-scanning. Three flavours dominate:

• Opposite ends (left=0, right=n-1) on a sorted array — pair-sum, container-with-most-water, palindrome checks.
• Same direction / fast-slow — one pointer scans, another marks a write position (remove duplicates, move zeroes).
• Two sequences — merge two sorted arrays or lists.

For opposite-ends pair-sum: if arr[l]+arr[r] is too small move l right, too large move r left. Each pointer moves at most n times → O(n).

Variant	Time	Space	Precondition
Opposite-ends pair sum	O(n)	O(1)	sorted
Fast-slow in-place filter	O(n)	O(1)	none
Merge two sorted arrays	O(n+m)	O(1)	both sorted
Sort then two-pointer	O(n log n)	O(1)	sortable

Exam Tricks & Tips

• 🎯 "Sorted array + find a pair/triplet" → opposite-ends pointers, skip the hash set.
• 🎯 3Sum = fix one element, two-pointer the rest → O(n²) beats O(n³).
• 🎯 In-place "remove/move" problems → slow pointer is the write index, fast pointer reads.
• 🎯 Skip duplicates by advancing while arr[l]==arr[l+1] to avoid repeated triplets.
• 🎯 Palindrome check: pointers from both ends moving inward, O(n) time O(1) space.
• ❌ Common mistake: using opposite-ends pointers on an unsorted array — sort first, or the move rule is invalid.

Expected pattern

"Find pair/triplet with target sum", "remove duplicates in place", "reverse/partition", or "container with most water". Interviewers expect you to justify why moving a specific pointer is safe (monotonicity) and to state O(n)/O(1).

Quick recap

Two pointers replace a nested loop: opposite ends on sorted data, fast-slow for in-place edits, or dual-sequence merge. Reduces O(n²)→O(n) with O(1) space — always argue why the pointer move is correct.

Cover the answer, recall, then check. 11 cards on the two-pointer pattern.

Q1. When does the opposite-ends two-pointer approach require a sorted array?
A1. For pair-sum / triplet problems — the move rule (small→l++, large→r--) is only valid on sorted data.

Q2. Pair-sum with two pointers: complexity?
A2. O(n) time, O(1) space (after the array is already sorted).

Q3. How does the fast-slow variant remove duplicates in place?
A3. Slow = write index; fast scans; when arr[fast] differs from arr[slow], increment slow and copy. O(n)/O(1).

Q4. Reduce 3Sum from O(n³) to O(n²) — how?
A4. Sort, fix element i, then two-pointer over the remaining subarray for target = -arr[i].

Q5. Move all zeroes to the end keeping order — pattern?
A5. Fast-slow: slow points to the next non-zero slot; swap non-zeros forward. O(n)/O(1).

Q6. Container With Most Water — which pointer moves?
A6. Move the pointer at the shorter line inward (the shorter wall caps area; moving the taller can't help).

Q7. Why does each pointer contribute only O(n)?
A7. Pointers only move toward each other and never reset, so total moves ≤ n.

Q8. Check if a string is a palindrome with two pointers?
A8. l=0, r=n-1; compare and move inward while l<r. O(n)/O(1).

Q9. Merge two sorted arrays with pointers — cost?
A9. O(n+m); one pointer per array, always take the smaller front element.

Q10. How to avoid duplicate triplets in 3Sum?
A10. After placing a value, skip identical neighbours (while nums[i]==nums[i+1]).

Q11. Most common two-pointer bug?
A11. Using opposite-ends pointers on an unsorted array, or an off-by-one in the l<r / l<=r loop bound.

Two pointers is the single highest-yield array pattern in coding interviews. It repeatedly turns an obvious O(n²) brute force into a clean O(n) scan by walking two indices instead of nesting two loops.

Core idea: keep two indices into the array and move them under a rule that never revisits a discarded possibility. Because each pointer advances at most n times, the whole scan is linear.

How it works

Beginner — the two flavours

• Opposite ends (converging): left = 0, right = n-1, move inward. Ideal on a sorted array or when comparing a pair from both sides (two-sum, palindrome check, container-with-most-water).
• Same direction (fast/slow): both start left; one races ahead while the other lags. Ideal for in-place filtering, removing duplicates, or partitioning.

Intermediate — why the converging scan is correct

Two-Sum on a sorted array: if a[left] + a[right] is too small, the smallest element can never pair with anything smaller than a[right], so left++ is safe. If too big, right--. Every move eliminates one element permanently, so at most n moves → O(n) time, O(1) space (versus O(n²) brute force or O(n) with a hash set that costs extra space).

left, right = 0, n-1
while left < right:
    s = a[left] + a[right]
    if s == target: return (left, right)
    elif s < target: left += 1
    else: right -= 1

Advanced — fast/slow for in-place work

"Remove all zeros, keep order" uses a write pointer that lags a read pointer:

write = 0
for read in 0..n-1:
    if a[read] != 0:
        a[write] = a[read]; write += 1

Read visits every slot once; write only advances on a keeper. O(n) time, O(1) space, and stable.

Worked example

Is "A man a plan a canal Panama" a palindrome (letters only)? Point left and right at the ends. Skip non-letters, lowercase, compare. Each character is visited once → O(n). They meet in the middle having matched every pair → palindrome. Brute-forcing by building the reverse string costs O(n) extra space; two pointers cost none.

When to use it

Signal words: sorted array, pair/triplet, palindrome, "in place", remove/partition, reverse. If a nested loop compares a[i] with a[j] where j only ever needs to move one way as i moves, two pointers collapse it to O(n). Triplet problems (3-Sum) fix one index and two-pointer the rest → O(n²) instead of O(n³).

Tricks & gotchas

• Converging pointers usually require the array to be sorted first (sorting adds O(n log n)).
• Guard the loop with left < right (pairs) or left <= right (searching a target).
• Mnemonic: "Sorted and pairs → squeeze from the ends."

Worked Example

Problem: In the sorted array [1, 3, 4, 6, 8, 10], find a pair that sums to 12 using two pointers.

Solution: Place pointer L at the start and R at the end. If the sum is too small, move L right (to increase it); if too big, move R left.

L (val)	R (val)	sum	action
0 (1)	5 (10)	11	11 < 12 → L++
1 (3)	5 (10)	13	13 > 12 → R--
1 (3)	4 (8)	11	11 < 12 → L++
2 (4)	4 (8)	12	12 = 12 → found

The pair is at indices 2 and 4, values 4 and 8.

Because each pointer only moves inward, the scan is O(n) — far better than the O(n²) brute-force pair check.

Answer: The pair (4, 8) at indices 2 and 4 sums to 12.