Two Pointers

1The mental model (what this really is)#

The whole idea in one line: instead of one index crawling through a sequence, you use two and move them with intent.

• Each pointer is just an integer index into an array or string.
• The two indices together carry more information than one index ever could.
• You advance one with purpose, and that purpose is always "I just ruled out a chunk of the search space."

There are two flavors you will meet again and again.

Opposite ends.

• One pointer starts left, the other starts right. They walk toward each other.
• You stop when they meet or cross.
• Shines when the data is sorted, or when the problem has symmetry (palindrome checks, reversing in place).

Same direction (fast and slow, or read and write).

• Both pointers start near the front.
• One races ahead to explore, the other trails behind marking a boundary.
• This is how you filter, compact, or measure a window in place.

Why it is so powerful.

• A naive solution checks every pair, which is O(n squared).
• Two pointers throws away huge chunks of that search space in one move.
• When you advance a pointer, you promise that everything you skipped cannot be the answer.
• That promise is the real skill. No justification for the skip means you do not have a two pointers solution yet, you have a guess that happened to pass the sample case.

2How to recognize it (the signals in a problem)#

Nobody tells you to use two pointers. You have to smell it. Here are the tells I teach every candidate.

• Sorted array plus "find a pair, triple, or relationship." Sorting plus "two things that add to X" is practically a neon sign.
• A string or array and a question about symmetry. Palindrome checks, reversing in place, comparing from both ends.
• "In place" or "O(1) extra space." That constraint almost always means a write pointer moving while a read pointer scans ahead.
• Longest or smallest contiguous run that satisfies a condition. That is the sliding window cousin: two pointers with bookkeeping between them.
• Brute force is nested loops over pairs, O(n squared), and you suspect better is wanted. On 10,000 elements that is 100 million comparisons versus 10,000. The gap is the point.
• Merging two sorted sequences, or comparing them element by element. One pointer per sequence.

The rule of thumb.

• If two or three of these fire at once, stop reaching for a hash map.
• Ask whether a pointer dance solves it cheaper, often at O(1) space instead of O(n).

3The template (how it works, with pseudocode)#

I keep two skeletons in my head. Memorize both. You adapt them, you do not copy them, but having the shape ready saves two minutes of fumbling under pressure, and those two minutes are often the difference between finishing and running out the clock.

Opposite ends:

left = 0
right = n - 1

while left < right:
    evaluate(arr[left], arr[right])

    if condition_met:
        record or return answer
    elif need_bigger_value:
        left += 1   # move the small side up
    else:
        right -= 1  # move the big side down

• The decision of which pointer to move is the entire problem.
• On an array sorted ascending, moving left right increases your value, moving right left decreases it. You steer toward the target.
• No reason for why a move gets you closer means you are not ready to write the loop yet.

Same direction (read and write, or fast and slow):

slow = 0   # boundary of the "good" region
for fast in range(0, n):
    if arr[fast] satisfies keep_condition:
        arr[slow] = arr[fast]
        slow += 1

# slow is now the length of the result

• fast explores every element exactly once.
• slow only advances when you commit to keeping something.
• The region before slow is always the clean, finished part of the array.
• The invariant "everything left of slow is final" is the sentence to say out loud.

Both skeletons run in one pass. That is the whole trick.

4A worked example (walk through one problem step by step)#

The classic: given a sorted array, find two numbers that add up to a target, return their indices.

• This is Two Sum II on LeetCode, and it is a genuine phone screen opener at Amazon and Microsoft.
• Input: [2, 4, 7, 11, 15], target = 9.
• A beginner checks every pair at O(n squared), ignoring the gift the problem handed over: the array is sorted. Sorted means I can reason about direction.

Set left = 0 (pointing at 2) and right = 4 (pointing at 15), then walk:

• Step 1. Sum is 2 + 15 = 17, bigger than 9. I need a smaller sum. The largest element is making it too big, so I shrink the big side. right moves to 3 (now 11).
• Step 2. Sum is 2 + 11 = 13. Still too big. Shrink again. right moves to 2 (now 7).
• Step 3. Sum is 2 + 7 = 9. Matches the target. Return indices 0 and 2. Done.

Why those skips were safe (this is the part you say out loud).

• Three steps, and I never touched 4 against anything, never touched 15 against 7.
• Watch step 1: the sum 2 + 15 was too big. Since 2 is the smallest value available, 15 paired with anything else can only be 17 or larger.
• So 15 can never be part of a valid pair. I drop it forever by moving right left.
• Every move eliminates an entire row or column of the pair grid. That is how O(n squared) collapses to O(n).

The trade to name unprompted.

• One pass. O(n) time, O(1) space.
• The sorting is what unlocks the direction logic.
• If the array came unsorted you would weigh sorting it (O(n log n)) against a hash map (O(n) time, O(n) space).
• Knowing that trade, and naming it before you are asked, is itself an interview point.

Every pointer move is a promise that what you skipped cannot be the answer. If you cannot prove the promise, you do not have the solution yet.

5Variations and gotchas#

Interviewers rarely hand you the vanilla version. Here is what they throw once you show you know the base pattern.

• Three pointers and fixing one element. For "three numbers that sum to a target," loop one pointer over the array and run the two pointer scan on the remainder. That is O(n squared), and it is the expected answer at Meta and Google. The pattern composes.
• Skipping duplicates. For unique triples, after you record an answer you must advance past repeated values on both sides, or you emit the same triple many times. This is the single most common place people lose points on 3Sum. Something like while left < right and arr[left] == arr[left+1]: left += 1.
• Fast and slow on a linked list. Move slow one node, fast two nodes. If they ever meet, there is a cycle. If fast hits the end, there is none. Same pattern, different medium. This also finds the middle node in one pass.
• Partitioning. The read-write template powers in-place partitions: move all zeros to the end, remove a target value, dedupe a sorted array. The write pointer is your output boundary.
• Merging. Two sorted lists, one pointer each, always consume the smaller head. This is the merge step of merge sort.

6Complexity#

State the complexity before anyone asks. It shows you know preprocessing is not free.

• Single scan (both opposite ends and same direction): you touch each element a constant number of times. O(n) time, O(1) extra space. No new arrays, no hash maps, just a couple of integers.
• Nested two pointers inside an outer loop (the 3Sum family): O(n squared) time, still O(1) or O(log n) extra space depending on whether you sorted in place.
• Sorting an unsorted input first to enable the pattern: add O(n log n) for the sort and O(1) to O(n) space depending on the sort. Always say this part.

7Mistakes that cost people the round#

The pattern is easy to state and easy to botch. These are the ones I see end interviews.

• Not justifying the skip. You move a pointer but cannot explain why the discarded options are provably wrong. I will poke exactly there. Rehearse the elimination sentence until it is automatic.
• Forgetting duplicates in unique-result problems. Instant correctness bug, and it is the one they test for on 3Sum.
• Off-by-one on the loop bound. < versus <=, or starting right at n instead of n - 1. Walk a two element and a one element array by hand before you say you are done.
• Reaching for two pointers on unsorted data without counting the sort cost. If you sort and lose the original indices the problem wanted, you just created a bug. Sometimes a hash map is the better call. Say why you chose what you chose.
• Moving both pointers at once when only one should move. In opposite-ends problems you advance exactly one side per iteration based on the comparison. Moving both can jump over the answer.
• Skipping the empty and single element inputs. These break naive loop bounds constantly, and silence on edge cases reads as sloppiness. I always ask "what happens on an empty array?" and the answer tells me a lot.

8Your practice path (named problems by difficulty)#

Do them in order. Each one adds exactly one new idea on top of the last.

Easy (learn the two skeletons):

• Two Sum II (Input Array Is Sorted)
• Valid Palindrome
• Reverse String
• Merge Sorted Array
• Remove Duplicates from Sorted Array
• Move Zeroes
• Squares of a Sorted Array

Medium (compose and add bookkeeping):

• 3Sum
• Container With Most Water
• Sort Colors (Dutch National Flag)
• 3Sum Closest
• Remove Nth Node From End of List
• Linked List Cycle II
• Partition Labels

Hard (stretch, same core idea):

• Trapping Rain Water
• Minimum Window Substring (the sliding window cousin)
• 4Sum

How to know you actually have it.

• Solve 3Sum cleanly from scratch, duplicates and all.
• Then explain Container With Most Water's pointer logic out loud.
• That is roughly ten focused problems, not a hundred. I would rather you grind those ten until the elimination argument is reflex than skim fifty.

9Where this shows up#

Two pointers is a staple of the phone screen and first onsite coding round almost everywhere.

• Amazon, Google, Meta, Microsoft, and the whole tier of high-bar startups lean on it.
• It is popular because it is quick to pose, has a clean optimal answer, and separates people who brute force from people who reason about why a shortcut is valid.
• You will rarely get a full round on it alone, but you will meet it early, and bombing an "Easy" two pointers problem is a fast way to end an interview before lunch.
• The sliding window extension shows up in medium coding rounds constantly, so the time you spend here pays off twice.

Want to see which companies lean hardest on this pattern and what their rounds actually look like? Check the company guides to map this skill to real interviews.