vizlearn
Home / Algorithms

Two Pointers

Algorithms & Data StructuresBy Updated

Two indices moving with purpose turn an O(n²) nested loop into a single O(n) pass. The trick only works when the data is ordered — and that ordering is what tells each pointer which way to move.

Controls

target sum16

Pointers in Motion

step 0

Insight

Two pointers work when moving one of them reliably changes the answer in a known direction. On a sorted array, moving left rightwards can only increase the sum.

comparisons0
brute force0
best so far–

Complexity

Two pointers O(n)
Brute force O(n²)
Space O(1)

Two Pointers

One pass instead of two nested loops — when the data lets you rule things out.

What this is

The two pointers technique uses two indices moving through a sequence in a coordinated way. It typically replaces a nested loop, turning O(n²) into O(n) with no extra memory.

The Classic: Pair Sum

Find two numbers in a sorted array that sum to a target. Brute force checks all pairs: O(n²). Two pointers starts one at each end:

  • Sum too small? Move the left pointer right — only larger values lie that way.
  • Sum too large? Move the right pointer left — only smaller values lie that way.
  • Exactly right? Done.

Each move eliminates an entire set of pairs from consideration without ever testing them. The pointers only ever move toward each other, so the whole search is one pass.

Why Sorting Is Essential

The technique depends on knowing what moving a pointer does. On a sorted array, moving left rightwards can only increase the sum — that guarantee is what makes it safe to discard everything you skipped.

On unsorted data no such guarantee exists, and the method is simply wrong. If your input is not sorted you must either sort first (O(n log n)) or use a hash set instead (O(n) time, O(n) space).

The three patterns

PatternPointersTypical use
Opposite endsStart and end, moving inwardsTwo-sum on sorted data, palindromes, container problems
Same directionBoth forward, at different speedsRemoving duplicates, partitioning in place
Fast and slowOne moves twice as fastCycle detection, finding the middle

Same direction is the in-place editing pattern. One pointer reads, the other writes:

def remove_duplicates(arr):          # arr is sorted; edit in place
    if not arr:
        return 0
    write = 1
    for read in range(1, len(arr)):
        if arr[read] != arr[write - 1]:
            arr[write] = arr[read]
            write += 1
    return write                     # new length

The invariant: everything before write is the deduplicated result so far. That framing — naming what is true about the region behind each pointer — is how these are reasoned about and debugged.

Fast and slow is the cycle-detection pattern, and the reason it works is worth understanding rather than memorising.

Container With Most Water

A subtler case worth understanding. Given heights, pick two lines forming the largest water container. Area is min(height) × width.

Start wide and always move the shorter line inward. Why is that safe? Moving the taller one can only reduce the width while the area stays capped by the same shorter line — so it can never improve. Moving the shorter one at least gives a chance of a taller limit. That single argument is what makes the greedy pointer movement correct.

Two indices instead of two loops

The two-pointer technique replaces a nested loop with two indices moving through the data, turning O(n²) into O(n).

It applies when the data has structure — usually sortedness — that tells you which pointer to move.

The canonical problem: find two numbers in a sorted array that sum to a target.

Brute force checks every pair: O(n²). With two pointers, one at each end:

Array [2, 7, 11, 15], target 18:

leftrightSumAction
21517Too small — move left right
71522Too large — move right left
71118Found

Three steps instead of six comparisons, and the saving grows with n. The logic is what makes it correct: if the sum is too small, the only way to increase it is a larger left value; if too large, a smaller right value. No possibility is skipped.

def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

Floyd's cycle detection

Move one pointer one step at a time and another two steps. If there is a cycle, the fast one laps the slow one and they meet. If there is no cycle, the fast one reaches the end.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Why they must meet: once both are inside the cycle, the gap between them closes by exactly one position per step, so it reaches zero. It cannot be jumped over.

The extension finds the cycle's start: after they meet, reset one pointer to the head and advance both one step at a time. They meet at the entry point. That result follows from the distances involved and is not obvious — it is worth trusting rather than deriving under time pressure.

The same technique finds the middle of a list in one pass: when the fast pointer reaches the end, the slow one is at the midpoint.

The two-pointer pair-sum is short enough to memorise without understanding it, and then it gets applied to unsorted data and silently returns nothing. The step worth examining is the one where a pointer moves: that move throws away candidates, and sortedness is the only thing that makes throwing them away safe.

example_01.pyPython
Output

                

                

                    
Guided tour

                    
  1. Run pair sum and step through. Watch each move discard a whole block of pairs the brute force would have tested.
  2. Compare the two counters. Two pointers does roughly n comparisons where brute force does n²/2.
  3. Change the target so no pair exists. The pointers still meet in one pass and correctly report failure.
  4. Try the palindrome check — the same converging pattern, comparing characters instead of summing.
  5. Run container with most water and watch it always move the shorter bar. That is the greedy choice the correctness argument justifies.

                

                

                    
Where that leaves you

                    
Two pointers replaces nested loops with a single coordinated pass, in O(1) extra space. It works only when moving a pointer changes the result predictably — usually because the data is sorted. Recognising that condition is the whole skill.

                

                

                    
Where it applies, and where it does not

                    
It applies when:
  • The array is sorted, or can be sorted cheaply.
  • The problem is about pairs or triplets satisfying a condition.
  • You are editing an array in place and want O(1) extra space.
  • The structure is a linked list and you need position without a length.
  • A monotonic condition tells you unambiguously which pointer to move.
It does not apply when:
  • The data is unsorted and sorting is not affordable.
  • Moving a pointer might skip a valid answer, because the condition is not monotonic.
  • The problem needs arbitrary lookups — a hash table is the right tool.
That last row is a real alternative worth naming. Unsorted two-sum is solved with a dictionary in O(n) and O(n) space:
def two_sum(arr, target):
    seen = {}
    for i, x in enumerate(arr):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
So the choice is: sorted input plus O(1) space (two pointers) against unsorted input plus O(n) space (hash table). Both are O(n) after sorting is accounted for.

                

                

                    
Three-sum, and the pattern that generalises

                    
The standard extension: find all triplets summing to zero. Sort, fix one element, and two-pointer the rest.
def three_sum(nums):
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i-1]:
            continue                          # skip duplicate first elements
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append((nums[i], nums[lo], nums[hi]))
                lo += 1
                while lo < hi and nums[lo] == nums[lo-1]:
                    lo += 1                   # skip duplicate second elements
                hi -= 1
    return out
O(n²) rather than the O(n³) of three nested loops. The duplicate-skipping lines are what most implementations get wrong, and they matter whenever the output must contain no repeats.
That structure — fix k−2 elements with loops, two-pointer the last two — generalises to four-sum and beyond, at O(n^(k-1)).

                

                

                    
                    
Sliding window is the same idea with both pointers moving forward and a condition maintained between them — used for subarray and substring problems.
Merging two sorted arrays uses one pointer per array, which is exactly merge sort's combine step.
In-place partitioning in quick sort is a same-direction two-pointer scan.
Dutch national flag uses three pointers to partition into three regions in one pass.
Recognising the family matters more than memorising each: all of them replace nested iteration with coordinated single-pass movement, justified by an invariant about the regions the pointers bound.

                

                

                    
Questions people ask

                    
Does the array need to be sorted? For opposite-end patterns, yes — the monotonic relationship is what justifies moving a pointer. Same-direction and fast-slow patterns do not require it.
Is sorting first worth the cost? Sorting is O(n log n) and two pointers is O(n), so the total is O(n log n) — still far better than O(n²), and it uses O(1) extra space where a hash table uses O(n).
How do I know which pointer to move? From the condition: if the current value is too small, move the pointer that increases it. If that is ambiguous, two pointers is not the right technique.
Why does Floyd's algorithm work? The gap between the pointers shrinks by one each step inside the cycle, so it must reach zero.
What is the space complexity? O(1) — just the two indices. That is the technique's main advantage over a hash-table solution.
Can it be used on a linked list? Yes, and fast-slow is designed for it — no random access needed.

                

                

                    
Recap in one screen

                    
  • Two coordinated indices replace a nested loop, turning O(n²) into O(n) with O(1) extra space.
  • Opposite ends for sorted-pair problems, same direction for in-place editing, fast-slow for cycles and midpoints.
  • Correctness comes from an invariant: what is guaranteed true about the region each pointer bounds.
  • Unsorted pair problems are usually a hash-table job instead — O(n) time, O(n) space.
  • Three-sum is a loop plus two pointers at O(n²), and skipping duplicates is the part that is easy to get wrong.

                

            


        

    

    


        
    



Run it in Python
Three uses of the same idea — pair sum, in-place duplicate removal, and palindrome checking — each with its pointer positions printed, and each replacing a nested loop.
two_pointers.pyPython 3
Output
How the code works
  1. while lo < hi:Strictly less than, so the two pointers never land on the same element — which would pair a value with itself. Every two-pointer loop lives or dies on this condition.
  2. if total < target: lo += 1The move is justified, not guessed. The list is sorted, so with a[hi] as the largest available partner, a[lo] cannot be part of any solution — discarding it is safe.
  3. lo += 1 / hi -= 1Each step eliminates a whole row or column of the pair table, so the n² candidates are covered in n steps. That is the trick, and it only works because the input is sorted.
  4. write = 1; for read in range(1, len(a)):The other variant: both pointers move forwards, at different rates. write marks the end of the kept prefix and read scans ahead — nothing is allocated.
  5. while lo < hi and not text[lo].isalnum():The inner skips also need the lo < hi guard, or a string of pure punctuation runs a pointer off the end. Nested pointer loops are where the index errors hide.
Change one thing
  • Shuffle data before calling pair_sum. It returns None for a pair that exists — sortedness is a precondition, not a nicety.
  • Print values in full after dedupe. The tail is stale data, which is why the function returns a length rather than a list.
  • Extend pair_sum to three numbers: fix one, two-pointer the rest. O(n²) instead of O(n³), and the standard answer to 3Sum.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Check yourself
0 of 3
Answer without scrolling back up.
  1. Pair-sum with two pointers requires the list to be:
  2. When the sum is too small, why is it safe to move lo right rather than hi left?
  3. In the in-place dedupe, why does the function return a length instead of a list?





 Cheat sheet
Two Pointers
Two indices moving with purpose turn an O(n²) nested loop into a single O(n) pass. The trick only works when the data is ordered — and that ordering is what tells each pointer which way to move.
ALGORITHMS · vizlearn.in/dsa/two_pointers.html
More in Algorithms
AlgorithmsSliding WindowAlgorithmsGreedy AlgorithmsAlgorithmsBacktracking Search MethodAlgorithmsDynamic Programming
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact