The Two Pointers Pattern

The tell

You are staring at a problem. The brute-force solution is two nested for loops — try every pair, O(n²). You feel like there has to be something better. Then you notice:

1. The array is sorted or you are allowed to sort it.
2. The condition you care about changes monotonically as you move an index — getting closer to zero, or farther from the target, or smaller/larger in a way you can reason about.

That is the two-pointer tell. The monotonicity is what lets you ditch the inner loop. Instead of "try all pairs," you say: "I know that moving the left pointer right makes the sum bigger, and moving the right pointer left makes it smaller — so at each step I only have one sensible move to make."

If the array is unsorted and you cannot sort it (say, the problem needs original indices), reach for a hash map instead. Two pointers and hash maps are the two canonical solutions to the same family of "pair" problems — the sorted structure of the array is what tips you to pointers.

Opposite-ends: the core template

def two_pointer_opposite(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]

        if current == target:
            return (left, right)        # found it
        elif current < target:
            left += 1                   # need a bigger sum
        else:
            right -= 1                  # need a smaller sum

    return None                         # no pair exists

Every opposite-ends problem has this skeleton. The invariant is: everything to the left of left has already been ruled out as a left candidate; everything to the right of right has been ruled out as a right candidate. When they cross, you have exhausted the search space in one pass.

The only thing that changes between problems is the condition and which pointer you move. Internalise the shape, then swap in the condition.

Worked problems

1. Two-sum on a sorted array

LeetCode 167. Given a sorted array, return the 1-indexed pair that sums to target. Guaranteed one answer exists.

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1

    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]   # 1-indexed output
        elif s < target:
            left += 1
        else:
            right -= 1

    return []   # per problem statement, unreachable

The sorted order is the secret. If numbers[left] + numbers[right] < target, there is no way any element to the left of left can help — they are all smaller. So left += 1 is the only legal move. Symmetrically for right. That argument is why we never need to revisit.

---

2. Valid palindrome

LeetCode 125. A string is a palindrome if it reads the same forward and backward (ignoring non-alphanumeric characters and case).

This is an opposite-ends problem on a string rather than a sorted array. There is no sorting here — the structure itself is symmetric.

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        # skip non-alphanumeric characters
        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

Notice the inner while loops that skip non-alphanumeric characters. They look like they might add a factor, but each pointer still travels at most n steps total — so it is still O(n). The skips happen in the same pass, not a nested second one.

---

3. Container with most water

LeetCode 11. Given an array of heights, find two lines that together with the x-axis form a container that holds the most water. The water volume is min(height[left], height[right]) * (right - left).

This is the one that feels hardest to justify. Why does moving the shorter wall inward always give us the right answer?

Think about it: the volume is limited by the shorter wall. If you move the taller wall inward, the width decreases and the height can only stay the same or decrease (since we are still limited by the shorter wall). So volume can only get worse. The only move that could give a bigger volume is moving the shorter wall, hoping to find a taller one.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0

    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)

        if height[left] < height[right]:
            left += 1      # shorter wall on the left, try a taller one
        else:
            right -= 1     # shorter wall on the right (or equal), move it

    return best

The visualizer makes this click immediately — watch the pointer movement and the area update with each step.

{ "type": "array", "title": "container with most water — which wall do you move?", "data": [1, 8, 6, 2, 5, 4, 8, 3, 7] }

Play through it step by step. Every time the shorter wall moves inward, you can see why the taller one staying put cannot improve the result.

---

4. Remove duplicates in place (slow/fast)

LeetCode 26. Given a sorted array, remove duplicates in-place and return the new length. O(1) extra space.

Here both pointers move forward — this is the slow/fast variant. fast reads every element; slow marks where the next unique value should land.

def remove_duplicates(nums):
    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]   # write the unique value

    return slow + 1   # new logical length

slow always sits at the last confirmed unique position. fast races ahead looking for the next different value. When it finds one, slow steps forward and takes the value. Because the array is sorted, all duplicates of a value are adjacent — so a single comparison nums[fast] != nums[slow] is sufficient.

No extra array. No shifting. Just two index variables and one pass. This is the pattern the arrays article uses in its worked example — go back and read that if you want to see the pointer movement spelled out visually.

---

5. 3Sum (the upgrade)

LeetCode 15. Find all unique triplets that sum to zero. This is the problem that trips people up in interviews because it looks like it must be O(n³).

The key insight: sort the array, then fix one element and run a two-pointer scan on the rest.

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # skip duplicate values for the fixed element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # now run opposite-ends on nums[i+1..n-1]
        left, right = i + 1, n - 1
        target = -nums[i]

        while left < right:
            s = nums[left] + nums[right]

            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                # skip duplicates before moving on
                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 s < target:
                left += 1
            else:
                right -= 1

    return result

Outer loop: O(n). Inner two-pointer scan: O(n). Total: O(n²) — versus the O(n³) brute force. And the sort cost is O(n log n), which is dominated by the O(n²) scan.

The trickiest part is the duplicate-skipping. If nums[i] equals nums[i-1], the outer triplets would be identical, so skip it. Inside the loop, after you find a valid triplet, skip consecutive equal values for left and right before advancing. Easy to get wrong under pressure — write it slowly.

The complexity picture

Variant	Time	Space	Requirement
Opposite-ends (pair sum, palindrome)	O(n)	O(1)	sorted or symmetric structure
Slow/fast (dedup, partition)	O(n)	O(1)	forward scan only
3Sum (sort + two-pointer)	O(n²)	O(1)	sort allowed
Brute-force pair search	O(n²)	O(1)	none
Brute-force triplet search	O(n³)	O(1)	none

Two pointers does not improve the exponent for 3Sum (n² is the best we can do without a fancy algorithm), but it removes one factor of n compared to the naive O(n³). That matters in practice — n² for n=1000 is a million operations; n³ is a billion.

Common mistakes

Off-by-one in the while condition. For opposite-ends: use while left < right, not left <= right. When left == right you are looking at the same element twice — that is not a pair. Exception: some problems (like finding the middle element or a specific palindrome center) do want left <= right; read the problem statement carefully.

Moving the wrong pointer. In container-with-most-water, some people always move right or always move left. The correct rule is always "move the shorter wall." If you cannot articulate why the pointer moves in your specific problem, you are guessing — slow down and reason from the monotonicity.

Forgetting to sort. Two-pointer on an unsorted array produces garbage. The correctness argument depends entirely on knowing that moving left increases the sum and moving right decreases it. Double check whether sorting is allowed. If indices matter (original positions needed in the output), two pointers is probably wrong and you want a hash map.

Duplicate triplets in 3Sum. If you skip the inner duplicate-skip loops, you will get the same triplet multiple times in the output. LeetCode will reject it. This is easy to forget when you are under time pressure — build the skip logic into your template and use it reflexively.

Using two pointers when the array is small enough for a hash map to be cleaner. Two pointers is elegant but it requires a sorted array. If someone gives you n=50 and an unsorted array and you start sorting + two-pointing, you have made the code harder to read for no measurable performance gain. Use the right tool for the situation.

How this connects to the rest of the course

Two pointers is close relatives with sliding window — both maintain two indices moving through the same array. The difference is intent and movement: two pointers usually closes in from opposite ends (or has a slow/fast pair) and works on pair/partition problems; sliding window expands and contracts a contiguous subarray and works on range/substring problems. It is worth learning both and knowing when each one fires.

When the array is sorted and you need to search rather than pair, think binary search before two pointers. Binary search finds a single target in O(log n); two pointers finds a pair relationship in O(n). Different tools for different shapes of question.

And everything here lives on top of arrays — understanding why index access is O(1) and why pointer arithmetic is cheap at the hardware level makes the "O(1) space" claim feel real rather than magic. Two pointers works because reading arr[left] and arr[right] is instant, and incrementing an integer is free.

When NOT to use two pointers

• Unsorted array, indices matter — use a hash map for O(n) with original positions preserved.
• You need all subarrays, not pairs — sliding window or prefix sums.
• The problem has more than two degrees of freedom — sometimes three pointers or a different structure fits better.
• The array is a linked list — two pointers still works (slow/fast for cycle detection, finding the middle, etc.) but you lose random access, so opposite-ends does not apply.
• n is tiny and code clarity matters more than performance — the nested loop is fine and it is easier to read.

If the problem does not have a sorted structure and does not have an obvious monotonicity argument, do not force two pointers. But when the tell is there — sorted array, pair/triplet/partition question — it is almost always the right move. Use it until you have a specific reason not to.