Two Pointer Technique: The O(n) Pattern That Kills the Nested Loop

You have a sorted array and you need to find two numbers that sum to a target. The obvious approach: a nested loop. For every element, scan the rest of the array for the complement. O(n²). Every interviewer has seen it a thousand times, and they're already writing "brute force" in their notes before you finish typing it.

Two pointers replace that nested loop with a single pass. Not because you skip checking pairs, but because the structure of a sorted array lets you eliminate entire classes of pairs in one step.

That's the heart of the technique: proof by elimination, not exhaustive search.

You reach for two pointers when you need to find a pair in a sorted array with a sum constraint, modify an array in place without extra memory, check a palindrome, or partition elements around a condition. The brute force is O(n²); two pointers is O(n). One of these gets you the job.

This energy. Right here. Don't be this person.

Two Variants, One Idea

The technique comes in two shapes, and mixing them up is the most common source of bugs.

Converging (opposite-ends): place one pointer at index 0, another at index n-1, move them toward each other. Use this for pair-sum problems on sorted arrays, palindrome checks, and area maximization. Requires sorted order or structural symmetry so each step makes a provably correct decision about which pointer to move.

Fast-slow (same-direction): both pointers start near the left. The fast pointer scans forward; the slow pointer marks the boundary of finalized work. Use this for in-place removal, partitioning, and linked-list cycle detection. No sorted-order requirement.

Top: converging, closing from both ends. Bottom: fast-slow, slow as the write cursor, fast as the reader.

Both variants share one property: each pointer moves in only one direction and never reverses. That's what makes O(n) possible regardless of what the condition at each step is.

Converging Inward or Chasing Forward?

Converging Pointers

Start with left = 0, right = n - 1. At each step, compute whatever property you care about using both elements. If the property is too small, advance left. If it's too large, retreat right. If it's exactly right, done.

Three steps. One direction per pointer. No going back.

The elimination argument is what makes this correct, not just fast. Suppose nums[left] + nums[right] < target. For any index j between left and right, nums[left] + nums[j] <= nums[left] + nums[right] < target because the array is sorted and nums[j] <= nums[right]. No pair starting at left can produce the target. Discard left entirely by advancing it. The same argument applies symmetrically when the sum is too large: no pair ending at right can work, so retreat it.

This only works on sorted arrays. On unsorted data, moving left forward could skip a valid pair.

Fast-Slow Pointers

slow marks the write cursor. fast scans for qualifying elements and hands them to slow.

# Remove duplicates from sorted array in place (LeetCode 26)
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

Everything at index <= slow is correct and final. Everything at index > slow is raw material for fast to inspect. When fast stops, slow + 1 is the length of the deduplicated prefix.

The finalized prefix grows one element at a time. The tail past slow is noise you throw away.

O(n) Time, O(1) Space: Why Every Bound Holds

Every row is O(1) space because pointers are just two integers on the stack. No auxiliary arrays. No recursion depth. The memory footprint is constant regardless of array length.

The O(n) Time Proof

For converging pointers: left starts at 0 and only increments. right starts at n-1 and only decrements. The quantity left + (n - 1 - right) increases by exactly 1 per iteration. The loop terminates when left >= right, so after at most n-1 iterations.

For fast-slow: fast increments once per loop body, from index 1 to n-1. That's n-1 iterations. slow moves at most as many times as fast (only when a qualifying element is found), so total pointer movement is at most 2(n-1) = O(n).

In both variants, O(1) work happens per iteration. Total time: O(n).

One Structure, Every Language

The canonical problem: Two Sum II (LeetCode 167). A 1-indexed sorted array, find two numbers summing to target, return their 1-based indices.

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

The Problems Two Pointers Was Built For

Two pointers fits a specific class of problems: ones where brute force checks every pair, but the structure of the data lets you prune entire candidates in one step.

Pair and triplet sums on sorted arrays. Two Sum II is the prototype. Three Sum extends it by fixing one element and running two pointers on the remaining sorted subarray. The structure generalizes: k-sum problems become sorting plus k-2 nested outer loops, each wrapping an O(n) two-pointer pass.

In-place array compaction. Remove elements satisfying some condition without allocating extra memory. The slow pointer tracks the valid prefix; fast finds the next keeper. This is the pattern behind standard-library remove-if idioms in most languages.

Palindrome and symmetry checks. Compare characters from both ends inward. Any mismatch fails immediately; reaching the center without failure means the string is a palindrome. O(n) time, O(1) space, no extra data structure.

Partition around a pivot. One pointer walks from the left looking for elements that belong on the right side; another walks from the right doing the opposite. Swap when both find candidates. This is the inner kernel of quicksort.

Maximum area and similar product-optimization problems. When area equals a product of two factors and you can reason about which factor to maximize at each step, two pointers can find the optimum in one pass. Container With Most Water is the canonical example.

Linked-list cycle detection. Fast and slow pointers on a list rather than an array. Floyd's algorithm is two pointers in a different memory layout: fast advances two nodes per step, slow advances one. When they meet, a cycle exists. The same O(n) argument applies.

How to Know You Need Two Pointers

When these signals stack up, two pointers is probably the right tool:

• The array is sorted, or sorting it doesn't change the answer
• The problem asks about pairs or triplets with a sum, difference, or product constraint
• In-place modification with O(1) space is required
• You need to compare elements at two positions simultaneously (palindrome, container)
• Brute force is O(n²) or O(n³) and the constraints suggest O(n) or O(n log n) is expected

Worked Example 1: Container With Most Water (LeetCode 11)

Problem: n vertical lines at positions 0 through n-1 with heights h[i]. Find two lines that together with the x-axis form the largest container. Area equals min(h[left], h[right]) * (right - left).

Why you reach for two pointers. Area has two factors: width (right - left) and height (min(h[left], h[right])). Starting at opposite ends gives maximum width. The question is whether moving inward can recover enough height.

The greedy decision: always move the shorter side inward. Here's the proof. Suppose h[left] <= h[right]. For any right' strictly between left and right:

area(left, right') = min(h[left], h[right']) * (right' - left)
                  <= h[left] * (right' - left)
                  <  h[left] * (right - left)
                   = area(left, right)

The first inequality holds because min <= h[left]. The second holds because right' - left < right - left. So area(left, right) is the best any pair using left as the left wall can do. We've already computed it. Move left forward.

def max_area(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        best = max(best, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

One pass. O(n) time, O(1) space.

The water fill shows the optimal container. Short left wall at index 0 gets discarded immediately. Left moves to index 1 (height 8), right stays at index 8 (height 7). Area = 7 x 7 = 49.

Worked Example 2: Three Sum (LeetCode 15)

Problem: Find all unique triplets in an unsorted array that sum to zero.

Why you reach for two pointers. Sort the array first (O(n log n)). Fix nums[i] as the first element. The problem reduces to: find a pair in nums[i+1..n-1] summing to -nums[i]. That's exactly Two Sum II on a sorted subarray. Run opposite-ends two pointers. Repeat for every i.

The duplicate skip is the tricky part. After sorting, identical values are adjacent. Skip nums[i] if it equals nums[i-1] (outer loop). After finding a triplet, skip all left duplicates and all right duplicates before advancing the pointers (inner loop). Without these skips, the same triplet appears multiple times in the output. Interviewers love asking why you need this and can tell immediately if you just copied the pattern.

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

Total complexity: O(n log n) for sorting plus O(n²) for the two-pointer passes combined: the outer loop runs O(n) times and each iteration runs an O(n) two-pointer sweep. Without two pointers, a brute-force triple loop is O(n³). The linear inner sweep is what buys you that factor of n.

Two triplets from one sorted pass. The duplicate skip at both left and right is what keeps the output clean.

Recap

• Two shapes: converging (opposite-ends) for pair sums and symmetry, fast-slow for in-place compaction and cycle detection
• Converging requires sorted order; the elimination argument breaks on unsorted arrays
• O(n) time because each pointer moves in one direction only, total movement bounded by 2n
• O(1) space because both pointers are stack integers, no auxiliary memory allocated
• Correctness is by elimination: each step discards an entire class of pairs that cannot be the answer
• Three-sum is O(n²) with two pointers, not O(n³), because the inner two-pointer pass is linear
• Container With Most Water: moving the shorter wall is a provable optimality argument, not a heuristic
• Fast-slow is the skeleton of the sliding window pattern and Floyd's cycle detection

If you want to practice explaining your pointer movement decisions out loud under interview conditions, SpaceComplexity runs voice-based mock interviews where the AI asks follow-up questions about your reasoning in real time. Saying "I advance left because no pair using it can sum to the target" is the difference between reciting the pattern and understanding why it works.

Two pointers and sliding window are closely related. The sliding window adds a constraint on what's inside the active range and shrinks from the left when the constraint breaks. Sliding Window Technique: Turn O(n²) Loops into O(n) in One Pass covers when to use each and how to tell them apart. If you want to see the same fast-slow idea applied to linked lists instead of arrays, Linked List Interview Questions: Reversals, Cycles, and the Hare That Catches Itself walks through Floyd's cycle detection and why two pointers at different speeds guarantee a meeting point.

Further Reading

• Two Pointers Technique, GeeksforGeeks
• Two Pointers problems, LeetCode
• In-place algorithm, Wikipedia
• std::vector, cppreference
• Array, MDN Web Docs
• Sorting algorithm, Wikipedia