Two Pointers: Turning O(n²) Pair Searches into O(n), and Why It Works

Introduction

Two pointers is a technique that uses two indices to efficiently traverse an array.

The brute-force way to examine pairs is a nested loop that checks all n(n−1)/2 of them. Two pointers checks at most about n pairs, and the reason it is still correct is the whole idea of the technique: each time a pointer moves, it discards a set of pairs that provably cannot contain the answer. Neither pointer ever moves backward, so together they take at most n steps.

That “provably” depends on a property of the input, almost always sorted order or non-negative values. When the property does not hold, the code still runs and returns a result. It is just wrong, without any error. So for every pattern below, it is worth knowing not only the code but the one-sentence argument for why a move is safe. That argument tells you when the pattern applies, and it is what interviewers usually probe with a follow-up question.

---

Two Pointers Basics

Pattern 1: Start from Both Ends

def two_sum_sorted(arr, target):
    """
    Find two numbers in sorted array that sum to target
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Increase sum
        else:
            right -= 1  # Decrease sum
    
    return []
# Test
arr = [1, 2, 3, 4, 6]
print(two_sum_sorted(arr, 6))  # [1, 3] (2+4=6)

Why O(n)?

Naive approach (nested loops):
for i in range(n):
    for j in range(i+1, n):
        if arr[i] + arr[j] == target:
            return [i, j]
Time: O(n²)
Two pointers:
left, right = 0, n-1
while left < right:
    # Move one pointer per iteration
Time: O(n)

Why each move is safe. Suppose arr[left] + arr[right] < target. Because the array is sorted, arr[right] is the largest value arr[left] can still be paired with. If even that sum is too small, then arr[left] paired with anything left in the range is too small, so left can be discarded forever. The mirror argument holds when the sum is too large: arr[right] plus the smallest remaining value is already too big, so right can go. Every step removes one index along with all of its remaining pairs, and no valid pair is ever skipped.

This argument uses sortedness in both directions, which is why the function silently fails on unsorted input (see Common Mistakes). It also explains why LeetCode 1 (Two Sum) is usually not solved this way: that problem gives an unsorted array and asks for the original indices. Sorting would cost O(n log n) and lose the indices, while a hash map of seen values solves it in one O(n) pass. Two pointers is the right tool when the input is already sorted, or when you need the values rather than their positions.

Pattern 2: Same Direction (Fast & Slow)

def remove_duplicates(arr):
    """
    Remove duplicates in sorted array (in-place)
    """
    if not arr:
        return 0
    
    write = 1  # Write pointer
    
    for read in range(1, len(arr)):  # Read pointer
        if arr[read] != arr[read - 1]:
            arr[write] = arr[read]
            write += 1
    
    return write
# Test
arr = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(arr)
print(arr[:length])  # [1, 2, 3, 4]

How It Works:

arr = [1, 1, 2, 2, 3, 4, 4]
Initial: write=1, read=1
Step 1: read=1, arr[1]=1 (duplicate, skip)
Step 2: read=2, arr[2]=2 (new, write), write=2
Step 3: read=3, arr[3]=2 (duplicate, skip)
Step 4: read=4, arr[4]=3 (new, write), write=3
Step 5: read=5, arr[5]=4 (new, write), write=4
Step 6: read=6, arr[6]=4 (duplicate, skip)
Result: [1, 2, 3, 4]

The same-direction pattern works for a different reason than the opposite-end one. Here read scans every element exactly once, and write marks the end of the part of the array that is already final. The invariant is: everything before write is the deduplicated answer so far, in order. Since write never passes read, overwriting arr[write] only ever destroys values that have already been read. This is why the operation needs no extra memory. The function returns the new length rather than shrinking the list, a convention inherited from C-style arrays: the elements after write are leftovers, not part of the result.

The read/write shape is one pattern with many applications, not a trick specific to duplicates. Change the “keep this element?” test and you get in-place filtering (keep elements matching a predicate, LeetCode 27 Remove Element) or moving zeros to the end (keep non-zeros, then fill the tail with zeros, LeetCode 283). None of these need sorted input, because the argument is about write never overtaking read, not about value order. Only the duplicate version needs sorting, since arr[read] != arr[read - 1] detects a new value only when equal values are adjacent.

def move_zeroes(arr):
    write = 0
    for read in range(len(arr)):
        if arr[read] != 0:
            arr[write], arr[read] = arr[read], arr[write]
            write += 1
    return arr

print(move_zeroes([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]

Swapping instead of overwriting keeps every original element in the array, so the zeros end up at the back and the non-zero elements keep their relative order.

---

Practical Problems

Problem 1: Three Sum

def three_sum(arr):
    """
    Find three numbers that sum to 0
    [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
    """
    arr.sort()
    result = []
    
    for i in range(len(arr) - 2):
        # Skip duplicates
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        
        left, right = i + 1, len(arr) - 1
        
        while left < right:
            total = arr[i] + arr[left] + arr[right]
            
            if total == 0:
                result.append([arr[i], arr[left], arr[right]])
                
                # Skip duplicates
                while left < right and arr[left] == arr[left + 1]:
                    left += 1
                while left < right and arr[right] == arr[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result
# Test
arr = [-1, 0, 1, 2, -1, -4]
print(three_sum(arr))
# [[-1, -1, 2], [-1, 0, 1]]

Step-by-Step Trace:

arr = [-4, -1, -1, 0, 1, 2] (sorted)
i=0, arr[i]=-4:
  left=1(-1), right=5(2): -4-1+2=-3 (< 0, left++)
  left=2(-1), right=5(2): -4-1+2=-3 (< 0, left++)
  left=3(0), right=5(2): -4+0+2=-2 (< 0, left++)
  left=4(1), right=5(2): -4+1+2=-1 (< 0, left++)
  left=5, right=5: stop
i=1, arr[i]=-1:
  left=2(-1), right=5(2): -1-1+2=0 ✅ → [-1,-1,2]
  left=3(0), right=4(1): -1+0+1=0 ✅ → [-1,0,1]
i=2, arr[i]=-1: skip (duplicate)

3Sum shows the standard way to extend the pattern: fix one element with an outer loop, then run two-sum on the rest. That gives O(n²) instead of the O(n³) triple loop, and the O(n log n) sort is negligible next to it. The same idea extends to 4Sum at O(n³).

Most wrong answers on this problem come from duplicates, not from the pointer logic. Two kinds of skipping are needed. Without the outer skip over equal arr[i] values, [-2, -2, 0, 0, 2, 2] returns [-2, 0, 2] twice, once for each -2. Without skipping past equal values after a match, [-2, 0, 0, 2, 2] returns it twice as well. (Strictly, skipping on one side after a match is enough: with arr[i] fixed, the left value determines the right one, so once the right side has moved to a new value, a repeated left value can no longer complete the same triple. Skipping both sides is the symmetric, easier-to-verify version.) Note also that arr.sort() sorts the caller’s list in place. In an interview that is usually fine, but in production code, sorting a copy (sorted(arr)) avoids surprising the caller.

Problem 2: Container With Most Water

def max_area(heights):
    """
    Maximum water between two lines
    """
    left, right = 0, len(heights) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        height = min(heights[left], heights[right])
        water = width * height
        max_water = max(max_water, water)
        
        # Move shorter side
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    
    return max_water
# Test
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(heights))  # 49

Why Move Shorter Side?

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
          L                       R
Current: width=8, height=min(1,7)=1, water=8*1=8
If move right (R--):
  width=7, height=min(1,3)=1, water=7*1=7 (worse)
If move left (L++):
  width=7, height=min(8,7)=7, water=7*7=49 (better!)
Lesson: Moving taller side never improves result

The general argument is the same as for sorted two sum. The water level is limited by the shorter line. If the left line is the shorter one, every container that uses it with some line closer than right is narrower, and its height is still at most heights[left]. So none of those containers can beat the one just measured, and the left line can be discarded. Moving the taller side instead might skip the optimal pair. When both lines are equal, moving either one is safe, which is why the code uses else.

This problem is a good example of why two pointers is hard to discover on your own: the input is not sorted, and the pattern works because of a different monotonic property (width only shrinks, so only a taller limiting line can help). Recognizing that kind of property is the real skill, and it is why I would practice by writing down the discard argument for each problem before writing code.

Problem 3: Subarray Sum

def subarray_sum(arr, target):
    """
    Count subarrays with sum equal to target (strictly positive values only)
    """
    left = 0
    current_sum = 0
    count = 0
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        # If sum > target, move left
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1
        
        if current_sum == target:
            count += 1
    
    return count
# Test
arr = [1, 2, 3, 4, 5]
print(subarray_sum(arr, 5))  # 2 ([2,3], [5])

This window approach depends on every value being strictly positive. Then adding an element always increases the sum and removing one always decreases it, so once the window sum exceeds the target, extending it further cannot help, and shrinking from the left is the only useful move.

Both failure cases are worth seeing. With negative numbers, a sum that is too large can come back down, so shrinking the window may skip valid answers. With zeros, the sum stays the same when the window changes, and several windows share one sum: subarray_sum([0, 5], 5) returns 1, but the correct answer is 2 ([0, 5] and [5]). The function does not crash in either case. It returns a plausible, smaller number. This is the version of the bug I would expect to reach production, because typical test inputs use small positive integers. For arrays that can contain zeros or negatives, use prefix sums with a hash map counting how often each prefix sum has appeared (LeetCode 560), which is O(n) without any assumption about signs.

---

Two Pointers Patterns

Pattern Summary

# 1. Start from both ends (sorting required)
left, right = 0, len(arr) - 1
while left < right:
    # Move left++ or right-- based on condition
# 2. Same direction (fast & slow)
slow = 0
for fast in range(len(arr)):
    # Move slow++ when condition met
# 3. Range search
left = 0
for right in range(len(arr)):
    # Process range [left, right]
    while condition:
        left += 1

When to Use Each Pattern

Pattern	Use Case	Example
Both ends	Two sum, palindrome	Sorted array search
Same direction	Remove duplicates, partition	In-place modification
Range search	Subarray sum, substring	Variable-length window

---

Advanced Techniques

Palindrome Check

def is_palindrome(s):
    """
    Check if string is palindrome (ignore non-alphanumeric)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True
# Test
print(is_palindrome("A man, a plan, a canal: Panama"))  # True

Partition Array

def partition(arr, pivot):
    """
    Move all elements < pivot to the front (order within each part not kept)
    [3,1,4,2,5], pivot=3 → [1,2,4,3,5], returns 2
    """
    left = 0
    
    for right in range(len(arr)):
        if arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
    
    return left
# Test
arr = [3, 1, 4, 2, 5]
pivot_idx = partition(arr, 3)
print(arr)  # [1, 2, 4, 3, 5]
print(pivot_idx)  # 2

A partition does not sort. It only guarantees that every element before the returned index is smaller than the pivot, and every element from that index on is greater than or equal to it. Within each side, the order is arbitrary: here 4 ends up before 3. That is the same partition step used by quicksort (the Lomuto scheme), which then sorts each side recursively. It is also the basis of quickselect for finding the k-th smallest element in average O(n), without sorting everything.

---

Where Two-Pointer Solutions Go Wrong

left < right or left <= right?

The condition depends on whether one element can form an answer on its own. For pairs, left < right is correct: left == right would pair an element with itself. For a palindrome check, left < right also works because the middle character of an odd-length string does not need a partner. For binary search, which also has two indices, left <= right is common because a single remaining element is still a candidate. When unsure, trace the smallest inputs (empty, one element, two elements) by hand before submitting. Getting it wrong rarely crashes: it either skips the last valid position or processes one index twice, and both only show up on those small edge cases.

Moving the wrong pointer

The other mistake I have made myself under time pressure is recognizing “two pointers” correctly and then moving the pointer on the wrong side, for example decrementing right when the sum is too small. Nothing crashes, and some test cases still pass, because the scan sometimes reaches the answer anyway. The check that prevents it is to ask, at every branch, which pointer’s value is responsible for the current result being wrong, and move only that one. In sorted two sum, a sum that is too small is left’s fault, because right is already the largest partner available. In Container With Most Water, the shorter line is at fault, because it caps the height.

Common Mistakes

# ❌ Wrong: Forgot to sort
arr = [3, 1, 4, 2, 5]
two_sum_sorted(arr, 6)  # Wrong result!
# ✅ Correct: Sort first
arr.sort()
two_sum_sorted(arr, 6)
# ❌ Wrong: Infinite loop
while left < right:
    if condition:
        # Forgot to move pointers!
        pass
# ✅ Correct: Always move pointers
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

---

Interview Tips

Most two-pointer problems in interviews are decided before any code is written. The questions worth asking out loud:

1. Is the input sorted, and am I allowed to sort it? If the problem asks for original indices (LeetCode 1), sorting destroys them and a hash map is usually better. If it asks for values or counts, sorting first is fine.
2. Which shape is it? Opposite ends (pair or palindrome), same direction read/write (in-place transform), or a growing and shrinking range (subarray or substring). Once the shape is clear, the code mostly follows the templates above.
3. What makes a move safe? Say the discard argument in one sentence. If you cannot, the pattern may not apply, and that is usually the follow-up question anyway.
4. Are duplicates allowed in the output? If not, plan the skip logic before writing the loop, as in 3Sum.
5. Can values be zero or negative? If yes, the positive-only window from Problem 3 is wrong, and prefix sums are the safer choice.

Then trace an empty array, a single element, and two elements before declaring the solution done.

---

Which two-pointer pattern fits

Pattern	Movement	Condition	Example
Both ends	left++, right—	Compare sum	Two sum
Same direction	slow++, fast++	Compare values	Remove duplicates
Range search	left++, right++	Window condition	Subarray sum

Every pattern relies on a guarantee that lets you discard a position for good. With pointers at both ends of a sorted array, a sum that is too small means nothing paired with the left element can work, so the left pointer moves. With a range, a sum that is too large means shrinking from the left is the only way to fix it, but that guarantee holds only when values are non-negative. With a negative number in the input, a larger window can have a smaller sum and the pointer logic silently misses answers; that case needs prefix sums and a hash map instead. Before using two pointers, say out loud why the position you are about to skip can never be part of an answer.

---

Recommended Problems

Baekjoon

• 2003: Sum of Numbers 2
• 1806: Subarray Sum

LeetCode

• LeetCode 167: Two Sum II (sorted input; compare with LeetCode 1, where a hash map is the better tool)
• LeetCode 15: 3Sum
• LeetCode 11: Container With Most Water
• LeetCode 26: Remove Duplicates from Sorted Array
• LeetCode 125: Valid Palindrome
• LeetCode 283: Move Zeroes

Programmers

• Jewelry Shopping

---

Related Posts

• Sliding Window
• Greedy Algorithms
• Arrays and Lists
• Stack and Queue
• Algorithm Series Full Index