Two-Pointer Reduction: Turning a Hard Problem Into an Easy One

Two-Pointer Reduction: Turning a Hard Problem Into an Easy One

Sometimes you meet a problem that does not look like a two-pointer problem at all. You cannot just put one pointer at the start and one at the end and start moving them. But with a small, clever change — like sorting the array — the same problem suddenly *becomes* a two-pointer problem. This trick is called two-pointer reduction: you "reduce" a tricky problem into a familiar one you already know how to solve.

These problems are usually labelled *medium* or *hard*, because the change you need to make is not obvious, and you must be careful: the answer to the new (changed) problem must also be the correct answer to the original problem. If that is true, you can solve the easy version and trust the result.

Four questions to ask yourself

Before you try a reduction, ask these questions. They help you discover whether a problem can be turned into a two-pointer problem:

1. Does the order of the items in the array matter?
2. Do we need to work with two items at the same time?
3. Does walking from both ends give us any special advantage?
4. Can we change (reduce) the problem into another problem? If yes, ask these same four questions about the new problem.

Let's see these in action.

The example problem: Two Sum

> Given an array arr of integers and a number target, find and return two elements whose sum equals target, if they exist.

For example, take this array and target = 13:

arr = [4, 1, 2, 7, 8, 5, 0, 6]

There are two pairs that add up to 13 here (for example 8 + 5). We want to find one such pair.

First attempt: the brute-force solution

The simplest idea is to try every possible pair. Pick one item, then check it against every other item. If any pair adds up to target, return them.

vector<int> twoSum(vector<int> &arr, int target) {
    // Use nested loop to find sum of all pairs
    for(int i = 0; i < arr.size(); i++) {
        for(int j = i + 1; j < arr.size(); j++) {
            if(arr[i] + arr[j] == target)
                return {arr[i], arr[j]};
        }
    }
    return {};
}

This works correctly. But it uses a loop inside a loop. If the array has n items, we check about n × n pairs. We say this takes O(n²) time. For large arrays this is slow. Can we do better?

Reducing it to a two-pointer problem

Let's answer our four questions for Two Sum:

• Q1. Does the order matter? *No.* We only need to find a pair with the given sum. We don't care where the numbers sit.
• Q2. Do we need two items at once? *Yes.* A sum always needs two numbers.
• Q3. Does walking from both ends help? *Not yet* — on a random, unsorted array, moving from both ends tells us nothing useful.
• Q4. Can we change the problem? *Yes!* Since the order does not matter (Q1), we are free to sort the array. Once it is sorted, the answer to Q3 changes completely.

After sorting:

arr = [0, 1, 2, 4, 5, 6, 7, 8]

Now place left at the start and right at the end. Because the array is sorted in non-decreasing order:

• Moving left to the right gives a bigger number, so the sum increases.
• Moving right to the left gives a smaller number, so the sum decreases.

This gives us full control over the sum, which is exactly what the two-pointer pattern needs.

The two-pointer algorithm

At each step compute sum = arr[left] + arr[right], then:

• If sum == target → we found our pair. Return it.
• If sum < target → the sum is too small. We need a bigger number, so increment left.
• If sum > target → the sum is too big. We need a smaller number, so decrement right.

Repeat while left < right.

#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int> &arr, int target) {
        // Sort the array in non-decreasing order
        sort(arr.begin(), arr.end());
        int left = 0;
        int right = arr.size() - 1;
        // Use a while loop to traverse the array using the two pointers
        while (left < right) {
            int sum = arr[left] + arr[right];
            // Found a pair that sums up to the target
            if (sum == target) {
                return {arr[left], arr[right]};
            }
            // ... if sum < target, left++; else right--;
        }
        return {};
    }
};

Walking through the sorted example (target = 13)

| Step | left value | right value | sum | action |

|------|-----------|------------|-----|--------|

| 1 | 0 | 8 | 8 | 8 < 13 → move left right |

| 2 | 1 | 8 | 9 | 9 < 13 → move left right |

| 3 | 2 | 8 | 10 | 10 < 13 → move left right |

| 4 | 4 | 8 | 12 | 12 < 13 → move left right |

| 5 | 5 | 8 | 13 | 13 = 13 → found 5 and 8! |

Notice how the two pointers steadily close the gap between them. The array is scanned only once, so the loop runs in about O(n) time. (Sorting costs O(n log n), which is still far better than O(n²).)

Why is this correct? (Proof of intuition)

The key idea: in every step we safely throw away one item forever, knowing it can never be part of the answer.

• When sum < target: arr[right] is currently the largest remaining number. If even pairing arr[left] with the largest number is still too small, then arr[left] paired with *any* other remaining number is also too small. So arr[left] can never reach target. We discard it by doing left++.

• When sum > target: arr[left] is the smallest remaining number. If even pairing arr[right] with the smallest number is still too big, then arr[right] paired with *any* other remaining number is also too big. So arr[right] can never reach target. We discard it by doing right--.

You might worry: "When we discard arr[right], did we miss its pair with an already-discarded item like arr[0]?" No — that pair was already checked back when arr[0] itself was discarded. So nothing is ever missed.

This is the invariant: we discard an item only after confirming none of its pairs can equal target. We keep going until we either find the pair, or all items are discarded (meaning no answer exists).

Where this pattern shows up

Two-pointer reduction is a whole family of problems. Once you can spot the reduction, many "hard" problems become routine. Examples include:

• Two sum
• Target limited two sum
• Duplicate aware two sum
• Largest container

The big lesson: when a problem doesn't fit the two-pointer template directly, ask the four questions. Often a small change — most commonly sorting — unlocks the simple, fast solution.