The Two-Pointer Pattern: Scanning an Array From Both Ends

The Two-Pointer Pattern

When you work with an array, you usually find what you need in one of two ways: either you already know the exact position (the index) of an item, or you walk through the array one item at a time using a loop. That walk is called a traversal.

Most of the time we traverse an array in a single direction — either from the first item to the last, or from the last item back to the first. Which direction we pick depends on the problem.

But some problems need us to look at items from both ends at the same time. The slow way to do this is with nested loops (a loop inside another loop). Nested loops re-check the same items again and again, which wastes time. The two-pointer technique gives us a much faster way.

What "two-pointer" means

A pointer here is just a variable that holds an index — it "points at" a position in the array. The two-pointer technique uses two of these variables, named left and right:

• left starts at the beginning, index 0.
• right starts at the end, index n - 1, where n is the size of the array.

Think of two fingers placed on a row of boxes: one finger on the first box, one on the last box. They move toward each other until they meet in the middle.

How the technique works, step by step

The general idea is simple:

1. Initialize left = 0 and right = n - 1 (so left < right).
2. Loop while left < right. On each pass:

• Look at arr[left] and arr[right] and do whatever the problem needs (compare them, add them, swap them, and so on).
• Move left forward by some number of steps if it should move.
• Move right backward by some number of steps if it should move.

1. Stop when the two pointers meet. The gap between them shrinks a little on every pass, so they are guaranteed to meet.

So the pointers start far apart and slowly close in:

left -> [ v1  v2  ...  ...  ...  vn ] <- right
            left moves right, right moves left, until they cross

A tiny example

Imagine the array arr = {10, 20, 30, 40}, so n = 4.

• Start: left = 0, right = 3. We look at arr[0] = 10 and arr[3] = 40.
• Move both inward: left = 1, right = 2. We look at arr[1] = 20 and arr[2] = 30.
• Now if we moved again, left would reach 2 and right would reach 1, so left < right is false. We stop.

In just two passes we touched every item. No nested loops were needed.

The generic code

Here is the shape of a two-pointer function (shown in C++). The helper functions incrementLeft, decrementRight, leftStep, and rightStep simply decide *whether* and *by how much* each pointer should move — and most of the time they are tiny and can be written directly inline.

void twoPointer(const vector<int>& arr) {
    // Initialize left and right to the ends of the array
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        int leftVal = arr[left];
        int rightVal = arr[right];
        // Check if the left pointer should be incremented
        if (incrementLeft(leftVal, rightVal)) {
            // Increment the left pointer by some steps
            left += leftStep(leftVal, rightVal);
            // ...
        }
        // similarly decide whether to move right
    }
}

Why it is fast (complexity)

• Time complexity: O(n). The two pointers together sweep across the whole array exactly once before meeting in the middle. That is one full pass, in both the best and worst case.
• Space complexity: O(1). We only use two extra variables. We never build a new data structure, so the extra memory stays constant no matter how big the array is.

This is the big win: a problem that might have needed nested loops (slow) can often be solved in a single linear pass with constant extra memory.

Where it is used

Many array problems fit the two-pointer pattern, but it is not always obvious how. They generally fall into three groups:

• Direct application — the two-pointer technique fits the problem as-is.
• Reduction — you first reshape the problem into an equivalent two-pointer problem, then solve it.
• Subproblems — the problem contains smaller parts, and one or more of those parts can be solved with two pointers.

Learning to recognize which group a problem belongs to is the real skill, and it comes with practice.