Articles

Two pointers is not a data structure or an algorithm. It is a way to move two indices through an array so that a nested-looking loop becomes a single pass. You have used it on this site already: the Reverse String exercise moves two indices from opposite ends, while Two Sum II moves them toward each other until they meet. This article gives that pattern a name, explains its speed, and separates its two families - converging and same-direction - so you can spot it in the next problem that calls for it.

The one rule that makes it fast

“Two pointers” means an algorithm keeps two indices into an array and moves each in one direction only. That is the definition. Be strict about it, because the one-direction rule is also the speed proof. The Guide to Competitive Programming states the method in a single sentence:

In the two pointers method, two pointers walk through an array. Both pointers move to one direction only, which ensures that the algorithm works efficiently.

The speed comes from counting. A pointer that only moves right takes at most $n$ steps, regardless of how the algorithm branches: there are $n$ positions, and the pointer never retreats. Two pointers therefore take at most $2n$ steps between them - $O(n)$ - even when the code looks like a loop inside a loop. Laaksonen makes the same point about the sliding window below: “While there is no useful upper bound on how many steps the pointer can move on a single turn, we know that the pointer moves a total of $O(n)$ steps during the algorithm, because it only moves to the right.” This is the same idea the amortized analysis article teaches: count the total across the whole run, not the worst single step. Here it applies to a loop instead of a data structure.

Two families, one pattern

The technique has two shapes. They differ in where the pointers start.

Converging: one pointer at each end, moving toward the middle. Use it when the array is sorted, or when you need to swap mirror positions.
Same-direction (sliding window): both pointers start at the left, and the window between them grows and shrinks. Use it when the question is about a contiguous range - a substring or subarray.

Both follow the same rule: each pointer moves one way, so the pair does $O(n)$ work. Only the meaning changes. The pointers can mark two ends of a shrinking search space, or two ends of a sliding window.

Converging: two sum on a sorted array

The site’s Two Sum II - Sorted Input is the canonical converging case. Given a sorted array and a target, put one pointer at the first element and the other at the last. Then use sortedness as a dial:

if the pair sums to less than the target, move the left pointer up - the only way to make the sum larger is a larger left value;
if it sums to more, move the right pointer down - the only way to make it smaller is a smaller right value;
if the pointers meet without hitting the target, no pair exists.

defmodule TwoSumII do
  def two_sum_ii(numbers, target) do
    values = List.to_tuple(numbers)
    converge(values, 0, tuple_size(values) - 1, target)
  end

  defp converge(_values, left, right, _target) when left >= right, do: []

  defp converge(values, left, right, target) do
    sum = elem(values, left) + elem(values, right)
    cond do
      sum == target -> [left + 1, right + 1]
      sum < target -> converge(values, left + 1, right, target)
      true -> converge(values, left, right - 1, target)
    end
  end
end

TwoSumII.two_sum_ii([2, 7, 11, 15], 9)

Trace [2, 7, 11, 15] with target 9. The left pointer starts at 2 and the right pointer at 15; their sum is 17, so move the right pointer down to 11, then to 7. The sum is 9, so the answer is [1, 2]. That takes three comparisons instead of the six pairs a nested loop would try. The difference grows with the array.

Sortedness makes each move safe. Moving the left pointer up can only increase the sum; moving the right pointer down can only decrease it. A comparison therefore does more than test one pair. It rules out an entire side of the search space. When the sum is too large, every pair using that left pointer and a smaller right pointer is dead. That elimination reduces the $O(n^2)$ “try every pair” search to $O(n)$ after an $O(n \log n)$ sort. The sort is the tax that makes the dial work.

The unsorted sibling shows why that tax exists. Plain Two Sum on an unsorted array cannot use converging pointers. Without order, you do not know which direction grows the sum, so moving either pointer is a guess. The unsorted version therefore uses the hash tables article instead and trades memory for a map that remembers what it has seen. Laaksonen notes the family resemblance: “many problems that can be solved using the two pointers method can also be solved using sorting or set structures, sometimes with an additional logarithmic factor.” Two pointers is the sort-and-scan version of a set lookup.

Converging again: reverse in place

The other converging use is swapping. The Reverse String problem asks you to reverse a list of characters with no extra space. Put one pointer at each end, swap their values, and step inward until they meet:

defmodule Reverse do
  def reverse(values) do
    arr = List.to_tuple(values)
    arr = swap(arr, 0, tuple_size(arr) - 1)
    Tuple.to_list(arr)
  end

  defp swap(arr, left, right) when left >= right, do: arr

  defp swap(arr, left, right) do
    {a, b} = {elem(arr, left), elem(arr, right)}
    arr = arr |> put_elem(left, b) |> put_elem(right, a)
    swap(arr, left + 1, right - 1)
  end
end

Reverse.reverse([?h, ?e, ?l, ?l, ?o])

This is the same technique doing a different job. It uses two pointers to transform something instead of find something, swapping one mirror pair at a time until the pointers meet. This is also where the language boundary matters. The problem statement says “in place with $O(1)$ extra memory,” which is a mutable-array promise. It belongs to languages where a list is a block of cells you can overwrite. Elixir’s lists are immutable, so the “swap” above builds a fresh tuple; there is no in-place mutation to save memory with. The algorithm - two pointers converging and swapping - stays the same. The memory contract belongs to the language, not the technique. Keeping those separate is the skill the reading Elixir article practices in general.

Same-direction: the sliding window

The second family starts both pointers at the left and lets the gap between them grow and shrink. The site’s Longest Substring Without Repeating Characters is the classic example: find the longest contiguous substring with no repeated character.

The window [left, right) stays valid through one invariant: it contains no repeats. Move the right pointer to grow it. When the new character is already inside, move the left pointer until the repeat is gone. The largest width seen along the way is the answer:

defmodule Window do
  def longest_unique_length(s) do
    chars = s |> String.graphemes() |> List.to_tuple()
    slide(chars, 0, 0, MapSet.new(), 0)
  end

  defp slide(chars, _left, right, _seen, best) when right >= tuple_size(chars), do: best

  defp slide(chars, left, right, seen, best) do
    char = elem(chars, right)
    if MapSet.member?(seen, char) do
      slide(chars, left + 1, right, MapSet.delete(seen, elem(chars, left)), best)
    else
      slide(chars, left, right + 1, MapSet.put(seen, char), max(best, right - left + 1))
    end
  end
end

Window.longest_unique_length("abcabcbb")

On "abcabcbb", the window grows through a, b, c to width 3. The second a is already inside, so the left pointer moves past the first a; the window becomes b, c, a, still width 3. It continues this way and never drops below the best width. The result is 3.

The complexity follows the same count, with the roles reversed. The right pointer advances $n$ steps total because it only moves forward. The left pointer advances at most $n$ steps too, since it never passes the right. The window may look like it can grow and shrink forever, but both pointers are monotone. The whole scan is $O(n)$ with a set for the window’s contents. The same-direction family is the converging family turned sideways: two ends chase each other across the array, and the invariant describes what lies between them.

The tell: when to reach for it

Two pointers is a shape you can recognize before writing code. Look for these signs:

Sorted input, and a pair or sum question - converging. The sortedness is what makes the “move left to grow, move right to shrink” dial honest.
“Contiguous”, “substring”, “subarray”, or “window” - sliding window, and the condition has to be monotone in the window: adding an element can only turn the invariant off, and removing one can only turn it back on.
In-place reversal or partition - converging swap, the mirror-pair transform.

Here is the limit: two pointers is a linear pass with a precondition. It usually needs sortedness - a $O(n \log n)$ tax paid up front - or a monotone condition, so each pointer knows which way to move. When the array is unsorted and the condition is not monotone, the technique does not apply. Use a map instead; unsorted Two Sum is the worked example of that boundary. The key question is simple: is the input ordered, or is the condition monotone? If neither is true, this is not a two-pointer problem.

Where to go next

Two Sum II - Sorted Input - the converging pair search, with the 1-indexing twist the problem adds on top.
Reverse String - the converging swap, and the in-place contract this article separated from the algorithm.
Longest Substring Without Repeating Characters
- the sliding window, where the monotone invariant is the whole solution.
Sorting: the wall at n log n - the tax most converging two-pointer solutions pay before they start.
Hash tables: the O(1) that has fine print
- the unsorted Two Sum’s home, and the trade two pointers avoids by sorting instead.
Amortized: the expensive step you almost never take
- the “count the total across the run” eye this article borrowed to prove the one-direction rule.
What O(n) actually promises - the growth shape the one-direction rule earns.

Two pointers is easy to miss because it is small: two indices, each moving one way, with a proof that they cannot do more than linear work. There is no clever structure to build and no recursion to unroll. The technique is a discipline: ask, for each pointer, does this pointer ever move backward? If the answer is no, you already have the complexity bound. Then decide what the two indices mean. They may be two ends closing on a target or two ends of a window moving forward. One pattern. One proof. When a sorted pair or a contiguous substring appears, you will know what to look for.

Two pointers: the pattern hiding in plain sight