Two Pointers

Two Pointers | Algoryva

First, the naive way

Check every pair

To find two values summing to a target, the obvious code tries every pair (i, j).

It forgets that the array is sorted. Once a[i] + a[j] is too small, pairing a[i] with any element left of j is hopeless, but the nested loops test those pairs anyway.

python

def pair_sum_naive(a, target):
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] + a[j] == target:
                return i, j
    return None

Cost: O(n²). For n = 2 × 10^5 that is about 2 × 10^10 pair checks.

Worked by hand

By hand

Sorted array [1, 2, 4, 7, 11, 15], target 13.

i	j	a[i]	a[j]	sum	action
0	5	1	15	16	too big: j = 4
0	4	1	11	12	too small: i = 1
1	4	2	11	13	found

1
Start at both ends
16 is over 13, and 15 is the largest value, so 15 cannot be part of any answer. Drop it.
2
Adjust the smaller side
12 is below 13, so 1 is too small to work with anything remaining. Drop it.
3
Match
2 + 11 = 13. Three looks rather than fifteen pair checks.

Implementation

Colliding pointers: pair with a target sum

Translate the observation directly into code.

Plan in plain steps

pseudocode

i = 0, j = n - 1
while i < j:
    s = a[i] + a[j]
    if s == target: found
    if s < target: i += 1
    else: j -= 1
not found

python

def pair_with_sum(a, target):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target:
            return i, j
        if s < target:
            i += 1
        else:
            j -= 1
    return None

print(pair_with_sum([1, 2, 4, 7, 11, 15], 13))   # (1, 4)
print(pair_with_sum([1, 2, 3], 100))   # None

Reading the code

›i < j (not <=) because a pair needs two *different* positions.
›Each branch moves exactly one pointer by one, so the gap j - i shrinks every iteration and the loop must end.
›Returning None after the loop means every index was eliminated without a match.

Implementation

Reader and writer: remove duplicates in place

For a sorted array, duplicates sit next to each other. The reader scans every element; the writer is the position where the next *new* value goes.

python

def remove_duplicates(a):
    if not a:
        return 0
    write = 1
    for read in range(1, len(a)):
        if a[read] != a[write - 1]:
            a[write] = a[read]
            write += 1
    return write

a = [1, 1, 2, 2, 2, 3]
k = remove_duplicates(a)
print(k, a[:k])   # 3 [1, 2, 3]

Reading the code

›write always points one past the last kept value, so a[:write] is the answer.
›We compare the reader to a[write - 1], the most recently kept value, not to a[read - 1].
›The reader never falls behind the writer, so writing never overwrites something not yet read.
›No extra list is created: O(1) extra space.

Implementation

One pointer per array: merge two sorted lists

Two sorted lists: always take the smaller front element. Each pointer only moves forward.

python

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

print(merge([1, 4, 9], [2, 3, 10]))   # [1, 2, 3, 4, 9, 10]

Reading the code

›Using <= keeps equal elements in their original order (the merge is stable).
›When one list runs out, the other's remainder is already sorted, so extend finishes the job.
›This is exactly the merge step of merge sort.

Worked problem

Three numbers that sum to zero

The problem

Given an array of integers, return all unique triplets [x, y, z] that sum to zero (no repeated triplets).

Sort the array.
Fix the first number by looping i. The remaining task is “find a pair summing to -a[i]” in the suffix, which is colliding pointers.
Skip equal values for i, and skip equal values after finding a match, to avoid duplicate triplets.
Total: O(n²): n choices for i times an O(n) pointer pass.

python

def three_sum(nums):
    nums = sorted(nums)
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        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:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return res

print(three_sum([-1, 0, 1, 2, -1, -4]))   # [[-1, -1, 2], [-1, 0, 1]]

Takeaway. Two pointers reduces “k-sum” by one dimension: fix one element, and a pair problem remains. Sorting first also makes duplicate-skipping easy.

Worked problem

Container with most water

The problem

Vertical lines stand at positions 0..n-1 with given heights. Choose two lines to form a container; its water is width × min(height). Find the maximum.

Start with the widest container (both ends).
The area is limited by the shorter line. Moving the *taller* pointer inward can only shrink the width and cannot raise the limiting height, so it can never help.
So always move the pointer at the shorter line, and track the best area.

python

def max_area(h):
    i, j = 0, len(h) - 1
    best = 0
    while i < j:
        best = max(best, (j - i) * min(h[i], h[j]))
        if h[i] < h[j]:
            i += 1
        else:
            j -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49

Takeaway. The core skill is arguing which pointer move can never lose the answer. Once you can state that argument, the code writes itself.

Wrap-up

Remember this

Two indices that only move forward turn many O(n²) pair searches into O(n).
Each pointer move must be justified: the discarded candidate can never be part of an answer.
Learn the five shapes: colliding, parallel, separate arrays, reader/writer, for-while.
Sort first when order is not given, and mind duplicates.
Pointers never back up, so total work stays linear even with a loop inside a loop.

Cheat sheet

Colliding: i=0, j=n−1; too small → i++, too big → j−−
Reader/writer: write marks the next slot; compare to a[write−1]
Merge: advance the pointer of the smaller front element
Cost: O(n) after sorting; O(n log n) with the sort
k-sum: fix k−2 elements, pointers for the last two: O(n^(k−1))
Needs: sorted order or a monotonic property

Top traps to avoid

Using colliding pointers on unsorted data.
Moving both pointers in the same step.
Forgetting the loop condition bounds (i < len(a)) on the reader or advancing pointer.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why is it safe to move i right when a[i] + a[j] < target in a sorted array?
2.What is the time complexity of colliding pointers on a sorted array of length n?
3.Sorted [1, 2, 4, 7, 11, 15], target 13. After comparing a[0] + a[5] = 16, which pointer moves?
4.Which task is best suited to reader/writer pointers?
5.In three_sum, why is the array sorted first?
6.merge([1, 4, 9], [2, 3, 10]) returns:
7.For a = [1, 2, 4, 7, 11, 15] and target 15, what does this print? i, j = 0, 5 while i < j: ... (move i up when the sum is small, j down when large)
8.After the standard in-place de-duplication (keep a write index k) on a = [1, 1, 2, 2, 3], what is printed?
9.What does reversing [1, 2, 3, 4] with two pointers print?
10.What is the largest water area for heights [1, 8, 6, 2, 5, 4, 8, 3, 7] (two pointers, move the shorter side)?
11.On a sorted array, why is it safe to move the left pointer right when the pair sum is too small?
12.A two-pointer scan over a sorted array of n items: what is the running time?
13.Using the write-index method, how many elements are left after removing every 2 from [3, 2, 2, 3]?
14.How many pairs in [1, 2, 3, 4, 5, 6] sum to 7, counted with two pointers?
15.Why must the array be sorted for the basic pair-sum two-pointer method?

Two Pointers

After this lesson you will be able to

Builds on

Unlocks

Two people searching a bookshelf from both ends

Check every pair

Order tells you which candidate to discard

Colliding pointers

By hand

The five shapes of two pointers

Colliding pointers: pair with a target sum

Reading the code

Reader and writer: remove duplicates in place

Reading the code

One pointer per array: merge two sorted lists

Reading the code

Why linear

Edge cases

Mistakes to avoid

How to spot two pointers

Three numbers that sum to zero

Container with most water

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core40 problems

Application17 problems

Challenge1 problem