Two pointers

A two-pointer algorithm keeps two indexes into the data and moves them according to simple rules. Each step moves at least one pointer, and neither ever moves back, so the whole thing is O(n). You already met one: the merge step of merge sort walks one pointer through each half.

There are two main shapes:

• Opposite ends: one pointer starts at the left, one at the right, and they move towards each other. Used on sorted data and for reversing or mirroring.
• Same direction (often called slow and fast, or read and write): both start on the left; one scans every item, the other moves only when something is kept.

Opposite ends: a pair with a given sum

In a sorted array, look at the smallest and the largest value. If their sum is too small, the smallest value is useless: even with the largest partner it does not reach the target, so move left forward. If the sum is too big, the largest value is useless, so move right back. Each step rules out one value for good.

1static (int, int)? PairWithSum(int[] sorted, int target)2{3    int left = 0, right = sorted.Length - 1;4    while (left < right)5    {6        int sum = sorted[left] + sorted[right];7        if (sum == target) return (left, right);8        if (sum < target) left++;      // need a bigger sum9        else right--;                  // need a smaller sum10    }11    return null;12}13 14int[] a = { 1, 3, 4, 6, 8, 9, 11, 14 };15Console.WriteLine(PairWithSum(a, 13));16Console.WriteLine(PairWithSum(a, 21)?.ToString() ?? "none");

(2, 5)
none

Compare with the dictionary version of the last lesson: both are O(n) time, but two pointers needs O(1) extra memory. The price is that the data must be sorted. If it is not, sorting first costs O(n log n).

Same direction: remove repeats in place

In a sorted array, repeats sit next to each other. A read pointer visits every item. A write pointer marks where the next value to keep goes. When read finds a new value, copy it to write and advance write. Nothing is shifted, and no second array is needed.

1static int RemoveDuplicates(int[] a)2{3    if (a.Length == 0) return 0;4    int write = 1;                          // a[0] is always kept5    for (int read = 1; read < a.Length; read++)6        if (a[read] != a[write - 1])        // a new value7            a[write++] = a[read];8    return write;                           // number of values kept9}10 11int[] spans = { 2, 2, 3, 3, 3, 5, 8, 8, 9 };12int n = RemoveDuplicates(spans);13Console.WriteLine(n);14Console.WriteLine(string.Join(", ", spans[..n]));

5
2, 3, 5, 8, 9

The same read/write shape filters an array in place for any condition: “keep only beams longer than 6 m”, “move all zeros to the end”. It is how List<T>.RemoveAll works internally, which is why RemoveAll is O(n) while calling Remove in a loop is O(n²).

Opposite ends: mirroring

Comparing or swapping the first and last item, then moving inwards, reverses an array or checks if text reads the same both ways. The pointers can also skip items, here spaces and punctuation:

1static bool IsPalindrome(string s)2{3    int i = 0, j = s.Length - 1;4    while (i < j)5    {6        if (!char.IsLetterOrDigit(s[i])) { i++; continue; }7        if (!char.IsLetterOrDigit(s[j])) { j--; continue; }8        if (char.ToLowerInvariant(s[i]) != char.ToLowerInvariant(s[j])) return false;9        i++; j--;10    }11    return true;12}13 14Console.WriteLine(IsPalindrome("Never odd or even"));15Console.WriteLine(IsPalindrome("Steel beam"));

True
False

When does two pointers apply?

1static int[] SortedSquares(int[] a)2{3    var result = new int[a.Length];4    int left = 0, right = a.Length - 1;5    for (int k = a.Length - 1; k >= 0; k--)6    {7        int l = a[left] * a[left], r = a[right] * a[right];8        if (l > r) { result[k] = l; left++; }9        else { result[k] = r; right--; }10    }11    return result;12}13 14Console.WriteLine(string.Join(", ", SortedSquares(new[] { -7, -3, 2, 3, 11 })));

4, 9, 9, 49, 121