Two Pointers Technique: Explained with Examples & Code

Many array problems ask about pairs: two numbers that add up to a target, two lines that hold the most water, two characters that should match in a palindrome. Checking every pair takes two nested loops. The two pointers technique replaces them with two indices that move through the input in one coordinated pass — and it comes in two shapes.

Why nested loops are too slow

Take a sorted array and ask whether any pair adds up to a target. Trying every pair costs about n²/2 checks: five billion for n = 100,000, against the hundred million or so simple operations a judge allows in a second. The brute force is correct, but it ignores the one fact that matters — the array is sorted.

Opposite ends: meet in the middle

Put left on the smallest value and right on the largest, and compare their sum with the target:

• Too big: move right one step left, to a smaller value.
• Too small: move left one step right, to a larger value.
• Equal: the pair is found.

Stop when the pointers meet. Each step moves one pointer inwards, so the loop runs at most n − 1 times.

1. The array is sorted, so left starts at the smallest number and right at the largest. All 21 pairs are still possible, and each comparison will rule out a whole group of them at once.
2. 1 + 15 = 16 is more than 14. 1 is the smallest number left, so 15 is too big with any partner: no pair can use it, and right steps left.
3. right moves to 11, ruling out 6 pairs at once. 1 + 11 = 12 is less than 14. 11 is the largest number left, so 1 is too small with any partner, and left steps right.
4. left moves to 2, ruling out 5 pairs at once. 2 + 11 = 13 is less than 14. 11 is the largest number left, so 2 is too small with any partner, and left steps right.
5. left moves to 4, ruling out 4 pairs at once. 4 + 11 = 15 is more than 14. 4 is the smallest number left, so 11 is too big with any partner: no pair can use it, and right steps left.
6. right moves to 8, ruling out 3 pairs at once. 4 + 8 = 12 is less than 14. 8 is the largest number left, so 4 is too small with any partner, and left steps right.
7. left moves to 6, ruling out 2 pairs at once. 6 + 8 = 14: found, at indices 3 and 4. Every step threw one number out for good, so it took 6 comparisons instead of 21 — O(n) time, O(1) space.

Why moving a pointer is safe

Lay every pair out as a triangle of sums, left value by row and right value by column. When arr[left] + arr[right] is too big, arr[left] is the smallest value still in play, so every pair that uses arr[right] is too big: its whole column can go. When the sum is too small, every pair that uses arr[left] is too small: its whole row goes. Each comparison discards a row or a column — never the answer.

1. Each cell is one pair, left value by row and right value by column, with its sum. Nested loops would check all 21. The pointers start at the top-right corner: the smallest value with the largest.
2. 1 + 12 = 13 is too big, and 1 is the smallest left value — so every cell in the 12 column is too big. The whole column is crossed out at once and right moves left.
3. 1 + 9 = 10 is too big, and 1 is the smallest left value — so every cell in the 9 column is too big. The whole column is crossed out at once and right moves left.
4. 1 + 7 = 8 is too small, and 7 is the largest right value still in play — so every cell in the 1 row is too small. The whole row goes and left moves down.
5. 3 + 7 = 10 is too big, and 3 is the smallest left value — so every cell in the 7 column is too big. The whole column is crossed out at once and right moves left.
6. 3 + 5 = 8 is too small, and 5 is the largest right value still in play — so every cell in the 3 row is too small. The whole row goes and left moves down.
7. 4 + 5 = 9: found after 6 comparisons instead of up to 21. Each step removed a row or a column, so the walk is a staircase of at most n − 1 steps: O(n).

That is the technique's invariant: if a valid pair exists, both of its values lie between left and right. It holds at the start, every move keeps it, and when the pointers meet with nothing found, it proves there is no pair. Facing a new two-pointer problem, the real work is finding the rule that lets you discard one end safely.

The code

The function returns the indices of a pair, or a "not found" marker; the program tries a target that exists and one that does not.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Indices of two values in a sorted array that add up to target,
// or {-1, -1} when no such pair exists.
pair<int, int> pairWithSum(const vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return {left, right};
        if (sum < target) left++;   // need a bigger sum: move the small end up
        else right--;               // need a smaller sum: move the big end down
    }
    return {-1, -1};
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 6, 8, 11};
    for (int target : {10, 100}) {
        pair<int, int> p = pairWithSum(arr, target);
        if (p.first == -1) {
            cout << "No pair adds up to " << target << "\n";
        } else {
            cout << "Pair found: " << arr[p.first] << " + " << arr[p.second] << " = " << target
                 << " (indices " << p.first << " and " << p.second << ")\n";
        }
    }
    return 0;
}

public class Main {
    // Indices of two values in a sorted array that add up to target,
    // or {-1, -1} when no such pair exists.
    static int[] pairWithSum(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) return new int[] {left, right};
            if (sum < target) left++;   // need a bigger sum: move the small end up
            else right--;               // need a smaller sum: move the big end down
        }
        return new int[] {-1, -1};
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6, 8, 11};
        for (int target : new int[] {10, 100}) {
            int[] p = pairWithSum(arr, target);
            if (p[0] == -1) {
                System.out.println("No pair adds up to " + target);
            } else {
                System.out.println("Pair found: " + arr[p[0]] + " + " + arr[p[1]] + " = " + target
                        + " (indices " + p[0] + " and " + p[1] + ")");
            }
        }
    }
}

def pair_with_sum(arr, target):
    """Indices of two values in a sorted list that add up to target, or None."""
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return left, right
        if total < target:
            left += 1   # need a bigger sum: move the small end up
        else:
            right -= 1  # need a smaller sum: move the big end down
    return None


arr = [1, 2, 3, 4, 6, 8, 11]
for target in (10, 100):
    found = pair_with_sum(arr, target)
    if found is None:
        print(f"No pair adds up to {target}")
    else:
        i, j = found
        print(f"Pair found: {arr[i]} + {arr[j]} = {target} (indices {i} and {j})")

// Indices of two values in a sorted array that add up to target, or null.
function pairWithSum(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++; // need a bigger sum: move the small end up
    else right--; // need a smaller sum: move the big end down
  }
  return null;
}

const arr = [1, 2, 3, 4, 6, 8, 11];
for (const target of [10, 100]) {
  const found = pairWithSum(arr, target);
  if (found === null) {
    console.log(`No pair adds up to ${target}`);
  } else {
    const [i, j] = found;
    console.log(`Pair found: ${arr[i]} + ${arr[j]} = ${target} (indices ${i} and ${j})`);
  }
}

Pair found: 2 + 8 = 10 (indices 1 and 5)
No pair adds up to 100

The same skeleton solves Two Sum II almost word for word. 3Sum fixes one number and runs this search on the rest, O(n²) instead of O(n³). Container With Most Water moves the shorter line, because the shorter line can never do better.

Same direction: read and write pointers

Here both pointers move left to right. read visits every element; write marks where the next element worth keeping goes. Everything before write is the finished answer, so the array is changed in place, with no second array. In Remove Duplicates from Sorted Array a value is worth keeping when it differs from the last one kept, nums[write - 1].

1. The first value is always kept, so write starts at index 1. Everything before write is the finished answer; read will look at every other element once.
2. read (index 1) finds 0, equal to the last kept value 0 — a duplicate. Only read moves on.
3. read finds 1, different from the last kept value 0: it is copied to index 1 and write moves to 2.
4. read (index 3) finds 1, equal to the last kept value 1 — a duplicate. Only read moves on.
5. read (index 4) finds 1, equal to the last kept value 1 — a duplicate. Only read moves on.
6. read finds 2, different from the last kept value 1: it is copied to index 2 and write moves to 3.
7. read (index 6) finds 2, equal to the last kept value 2 — a duplicate. Only read moves on.
8. read finds 3, different from the last kept value 2: it is copied to index 3 and write moves to 4.
9. read (index 8) finds 3, equal to the last kept value 3 — a duplicate. Only read moves on.
10. read finds 4, different from the last kept value 3: it is copied to index 4 and write moves to 5.
11. read has passed the end. The first 5 slots hold every distinct value in order, [0, 1, 2, 3, 4], with no second array: O(n) time, O(1) space.

#include <iostream>
#include <vector>
using namespace std;

// Keeps one copy of each value at the front of a sorted array, in place.
// Returns how many values were kept.
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int write = 1;                          // next free slot for a new value
    for (int read = 1; read < (int)nums.size(); read++) {
        if (nums[read] != nums[write - 1]) { // a value not kept yet
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

int main() {
    vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    int k = removeDuplicates(nums);
    cout << "Unique values: " << k << "\n";
    cout << "Front of the array:";
    for (int i = 0; i < k; i++) cout << " " << nums[i];
    cout << "\n";
    return 0;
}

public class Main {
    // Keeps one copy of each value at the front of a sorted array, in place.
    // Returns how many values were kept.
    static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int write = 1;                          // next free slot for a new value
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[write - 1]) { // a value not kept yet
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int k = removeDuplicates(nums);
        System.out.println("Unique values: " + k);
        StringBuilder front = new StringBuilder("Front of the array:");
        for (int i = 0; i < k; i++) front.append(" ").append(nums[i]);
        System.out.println(front);
    }
}

def remove_duplicates(nums):
    """Keep one copy of each value at the front of a sorted list, in place.
    Return how many values were kept."""
    if not nums:
        return 0
    write = 1                          # next free slot for a new value
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:  # a value not kept yet
            nums[write] = nums[read]
            write += 1
    return write


nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(nums)
print("Unique values:", k)
print("Front of the array:", *nums[:k])

// Keeps one copy of each value at the front of a sorted array, in place.
// Returns how many values were kept.
function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let write = 1; // next free slot for a new value
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {
      // a value not kept yet
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
}

const nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
const k = removeDuplicates(nums);
console.log(`Unique values: ${k}`);
console.log(`Front of the array: ${nums.slice(0, k).join(" ")}`);

Unique values: 5
Front of the array: 0 1 2 3 4

Only the rule for "worth keeping" changes in Move Zeroes (keep the non-zero values, then fill the tail with zeroes) and Remove Element (keep everything that is not the given value).

Fast and slow pointers

Move one pointer a step at a time and the other two. If the sequence loops back on itself, the fast pointer laps the slow one inside the loop and they meet; if it does not, fast simply reaches the end. This is Floyd's cycle detection, used on linked lists and on number sequences such as Happy Number.

1. Both pointers start at the head. Node 6 links back to node 3, so following next pointers never reaches the end — the list has a cycle.
2. Step 1: slow moves one node to 2, fast moves two to 3.
3. Step 2: slow moves one node to 3, fast moves two to 5. Both are inside the loop now; fast is behind slow going round, and gains one node every step.
4. Step 3: slow moves one node to 4, fast moves two to 3.
5. Step 4: slow moves to 5 and fast jumps two nodes to 5 — they meet. Inside a loop the fast pointer closes the gap by one node a step, so it can never jump over the slow one.
6. Meeting proves a cycle (positions 2/3, 3/5, 4/3 and 5/5 as slow/fast): without one, fast would simply reach the end. It takes O(n) steps and two pointers, where a set of visited nodes would need O(n) memory.

Other shapes of the same idea

• Two arrays: one pointer in each, always taking the smaller front value — the merge step of merge sort, and Merge Sorted Array filled from the back.
• Squares of a sorted array: with negatives, the largest square sits at one of the two ends, so the result fills from its back — see Squares of a Sorted Array.
• Palindromes: compare the first and last characters and move both inwards; any mismatch settles it.
• Partitioning: three pointers sort values below, equal to and above a pivot into three bands in one pass, as in Sort Colors.

Time and space complexity

Neither pointer ever moves backwards, so between them they make at most n moves. On unsorted input a hash set also finds a pair in O(n), at the cost of O(n) memory — see Hashing. Two pointers wins when the input is already sorted, when extra memory is forbidden, or when the values must come back in order.

How to recognise a two-pointer problem

• The input is sorted, or sorting it would not change the answer.
• The question is about a pair or a triplet meeting a condition: a sum, a difference, an area.
• The statement says in place or O(1) extra space — that nearly always means read and write pointers.
• A sequence is compared with its own reverse, or processed from both ends.

If the question is about a contiguous run — the longest substring without repeats, the smallest subarray with a sum of at least k — you want the Sliding Window, the same-direction special case. If one value must be found many times, try Binary Search.

Common mistakes

• left <= right instead of left < right: both pointers on one element pair a value with itself.
• Forgetting to sort: opposite-end pointers on unsorted data give wrong answers silently. To return original indices, sort (value, index) pairs.
• Moving the wrong pointer: a sum that is too big rules out the larger value, so right moves.
• Duplicates in 3Sum: skip equal values after recording a triplet, or the same triplet is reported twice.
• Overflow: two values near the integer limit overflow when added in C++ or Java; compare arr[left] with target - arr[right] instead.

Practice in this order

1. Reverse String: opposite ends, swap and move both.
2. Move Zeroes: read and write pointers.
3. Remove Duplicates from Sorted Array: the animation above.
4. Merge Sorted Array: one pointer per array, filled from the back.
5. Two Sum II: the first program above.
6. 3Sum: an outer loop around a two-pointer search, with duplicates to skip.
7. Container With Most Water: a discard rule you have to prove.
8. Trapping Rain Water: two pointers that carry a running maximum each.

Every two-pointer problem in the catalogue is on the two pointers problem list, easiest first. When the first six feel routine, move on to the next stage of the roadmap: the sliding window.