Two Pointer Algorithm: How One Realization Kills the Nested Loop

You have a sorted array. You need two numbers that sum to a target. Natural first move: for every element, scan the rest of the array for a match. Two loops, every pair, O(n²). It works. It also gets you killed at n = 10,000.

The two pointer algorithm is the observation that sorted order lets you eliminate entire classes of candidates in a single step. No extra memory. No second loop. O(n) time. Once you see why it never misses the answer, you'll recognize the pattern in a dozen different problems.

---

Your First Instinct Is Almost Always O(n²)

The pair-search problem is a great starting point because the brute force is so obvious it hurts a little. Fix one index, scan everything to its right. Every pair gets checked. Nothing gets skipped early, even when sorted order is basically waving a red flag telling you to stop.

The problem isn't correctness. It's wasted work. You have a sorted array and you're ignoring the sort. That's like having GPS and still stopping to ask for directions because it's more comfortable.

---

The Two Pointer Algorithm in One Pass

You maintain two index variables and advance them based on what you observe. They can start at opposite ends and converge toward the middle (the converging variant), or they can start at the same end and move at different speeds (the fast-slow variant).

The converging skeleton in Python:

def converging_template(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        # examine arr[left] and arr[right]
        if some_condition:
            return result
        elif need_larger:
            left += 1
        else:
            right -= 1

The loop structure is always the same. The intelligence lives in which pointer you move and why.

---

Converging Pointers: Two Sum II

LeetCode 167 is the canonical starting point. Given a sorted array, find the two indices whose values sum to a target.

def two_sum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left + 1, right + 1]  # problem uses 1-indexed output
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

Trace through [2, 7, 11, 15], target 9:

Step	left	right	sum	action
1	0 (val 2)	3 (val 15)	17	too large, move right left
2	0 (val 2)	2 (val 11)	13	too large, move right left
3	0 (val 2)	1 (val 7)	9	match

Three steps. No revisiting. The brute force would've checked six pairs to arrive at the same answer.

---

Why It's Correct: The Elimination Argument

This is the part most explanations skip, and it's what interviewers actually want to hear.

When the sum is too small and you advance left, you're provably eliminating every pair that involves the current left value paired with anything smaller than the current right value. The array is sorted. Moving right leftward would only decrease the sum further. There's no point. So you can rule out all those pairs at once.

The same logic runs in reverse: when the sum is too large and you move right leftward, you've eliminated every pair with the current right element paired with anything larger than current left.

The formal invariant: at every step, the correct answer (if it exists) is still reachable from the current pointer positions. Neither pointer has passed it.

This is why sorted order is required. Without it, "moving left rightward makes the sum larger" isn't guaranteed, and the whole argument collapses. An unsorted array can't be systematically pruned because each step could go anywhere. The algorithm works because the array is honest: bigger index means bigger value, always.

---

Fast-Slow Pointers: Remove Duplicates

The second variant keeps both pointers moving in the same direction at different speeds. The slow pointer owns the output section of the array. The fast pointer reads ahead.

LeetCode 26: remove duplicates from a sorted array in-place.

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

slow marks where the next unique element should go. fast scans forward. When it finds something new, slow advances and writes it. When fast finds a duplicate, it just moves on. One pass, no extra array.

The same shape handles "remove element," finding the linked list midpoint (one pointer moves one step, the other moves two), and Floyd's cycle detection. Different speeds, same split between a reader and a writer.

---

Time and Space

Almost every two-pointer solution is O(n) time and O(1) space. Each pointer traverses the array at most once. Two integers. Nothing that scales with n.

Compare to the common alternatives for pair-search:

Approach	Time	Space	Requires sorted input?
Brute force (nested loops)	O(n²)	O(1)	No
Hash map	O(n)	O(n)	No
Two pointers	O(n)	O(1)	Usually yes

Two pointers matches the hash map on time but wins on space. That's the sweet spot when the input is already sorted, or when sorting first is allowed.

One caveat: if you have to sort an unsorted input, you're paying O(n log n) upfront. For problems like 3Sum, that's the honest total complexity even though the pointer scan itself is linear. Don't wave your hands at that part in an interview. They notice.

---

Extending the Pattern: 3Sum

Once converging two pointers is natural, 3Sum (LeetCode 15) is a straightforward extension. Fix one element with an outer loop, then run two pointers on the subarray to the right.

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

Overall complexity: O(n²) after the O(n log n) sort. The naive approach is O(n³). For n = 3,000, that's 9 million operations versus 27 billion. The difference between something that ships and something your tech lead quietly rewrites over lunch.

The duplicate-skipping logic (the inner while loops) is where most first attempts break. After finding a valid triple, you advance both pointers and skip repeated values to avoid outputting the same triple twice. Skip this step and your output is "correct" until a test case with repeating numbers shows up and suddenly you're submitting five identical [-1, -1, 2] entries.

---

When to Reach for Two Pointers

A few signals that converging two pointers is the right tool:

Sorted array, find two or more elements satisfying a sum or distance condition. Sorted input is the tell. The problem is almost certainly two pointers or sliding window, depending on whether you need a variable-size window.

"In-place" modification. Fast-slow pattern. Slow pointer owns the output; fast pointer reads. Remove duplicates, remove element, move zeroes to the end. All the same shape.

Linked list structural questions. Finding the kth node from the end (advance one pointer k steps first, then move both), detecting a cycle (Floyd's), finding the midpoint. Fast-slow at different speed ratios.

"Maximize area / minimize distance between two elements." Container With Most Water (LeetCode 11) is the classic. Move whichever pointer points to the shorter line, because keeping the shorter line can never increase the area.

Brute force is O(n²) and obvious. That's often the hint that one loop can be replaced by a pointer moving monotonically through the search space.

---

Mistakes Worth Knowing

Forgetting to sort. The elimination argument requires sorted input. Unsorted array where sorting isn't allowed? You probably want a hash map. Two pointers on an unsorted array is just random pointer movement with extra steps.

Moving both pointers on a match without skipping duplicates. 3Sum requires advancing past repeated values after a valid triple. Skip this and you get duplicate output. The problem statement says "return all unique triplets" and you'll return duplicates. Embarrassing.

Using left <= right instead of left < right. When the pointers are equal, they're on the same element. Most pair-search problems want two distinct indices. Equal pointers is not a pair. It's just one pointer pretending really hard.

Applying two pointers to the original Two Sum (LeetCode 1). The unsorted version wants O(1) lookups. Sort plus two pointers technically works but costs O(n log n) when a hash map gives O(n). A correct-but-suboptimal answer to a problem with a well-known optimal solution is its own kind of wrong.

---

Say the Elimination Argument Out Loud

Knowing the pattern is half the job. Stating the reasoning before you code is the other half.

Don't just say "I'll use two pointers." Say: "The array is sorted. If the current sum is too small, moving right leftward only makes it smaller, so the only productive move is advancing left. That means I can safely eliminate every pair involving the current left value paired with a smaller right value."

That one sentence is what gets written on the feedback form. It's the difference between a checkmark in "problem solving" and a blank. The interviewer already knows two pointers works. They're waiting to find out if you know why, because "why" is the signal that transfers to problems you haven't seen before.

If explaining your reasoning under pressure feels harder than solving the problem, that's worth practicing specifically. SpaceComplexity runs voice-based mock interviews with rubric-based feedback on exactly this dimension. Solving a problem at your desk and narrating your approach to an interviewer are different skills, and only one of them shows up on the feedback form.

---

Further Reading

• LeetCode 167: Two Sum II, the converging two pointer starting point
• LeetCode 15: 3Sum, extends the pattern to three elements, adds duplicate-skipping complexity
• LeetCode 11: Container With Most Water, tests whether you can state the elimination argument for a non-sum condition
• GeeksforGeeks: Two Pointer Technique, walkthrough with additional examples and diagrams
• Two Pointers vs Sliding Window, when the two patterns look identical and how to tell them apart