Two pointers

The pattern

Two indices walk the array instead of one. Usually they start at opposite ends and move toward each other; sometimes both start at the left and one runs ahead.

It works when the array is sorted, or when the order itself carries the information you need. The reason it is fast: at every step you rule out a whole group of possibilities with one comparison, instead of testing them one by one.

Recognise it from these phrases in a question: sorted array, find a pair, remove in place, palindrome, without extra space.

The problem

Given a sorted array of integers and a target, return the 1-based indices of the two numbers that add up to the target. Exactly one solution exists.

nums = {2, 7, 11, 15}, target = 9 -> {1, 2}

Step 1: the brute force

Always state this in an interview before optimising. It shows you understand the problem, and it gives you a baseline to beat.

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

vector<int> two_sum_brute(const vector<int> &nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (nums[i] + nums[j] == target)
                return {i + 1, j + 1};
    return {};
}

O(n^2) time, O(1) space. Correct, but for n = 100,000 it is 5 billion comparisons.

Step 2: notice what sorting gives you

The array is sorted and we have not used that fact once. Put one pointer at each end.

nums = {2, 7, 11, 15}, target 9. left = 0, right = 3.

Sum is 2 + 15 = 17, too big. Now think about what that tells you. 15 is the largest value in the range. Even paired with the smallest, it overshoots. So 15 cannot be part of any valid pair at all. Discard it: right--.

That single comparison eliminated three pairs, not one. That is where the speed comes from.

Symmetrically, if the sum is too small, the left value is too small to work with anything remaining, so left++.

Step 3: the code

vector<int> two_sum_sorted(const vector<int> &nums, int target) {
    int left = 0;
    int right = (int)nums.size() - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target)      return {left + 1, right + 1};
        else if (sum < target)  left++;      // need a bigger sum
        else                    right--;     // need a smaller sum
    }
    return {};       // no pair
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    vector<int> ans = two_sum_sorted(nums, 9);
    cout << ans[0] << " " << ans[1] << "\n";     // 1 2

    vector<int> big = {1, 3, 4, 5, 7, 11};
    vector<int> a2 = two_sum_sorted(big, 9);
    cout << a2[0] << " " << a2[1] << "\n";       // 3 4  (4 + 5)
    return 0;
}

O(n) time, O(1) space. left only increases and right only decreases, so together they move at most n steps.

Step 4: prove it does not miss the answer

This is the follow-up question, and most candidates cannot answer it.

Claim: the pointers never skip the correct pair. Suppose the answer is (i, j). The pointers start outside that range, at 0 and n-1. We only ever move left right when nums[left] is provably too small for anything remaining, so left can never move past i before right reaches j. The same for right. So the pair is still inside the window when we reach it.

The same pattern, different shape

Both pointers from the left, one fast and one slow. Remove duplicates from a sorted array in place and return the new length.

int remove_duplicates(vector<int> &nums) {
    if (nums.empty()) return 0;
    int slow = 0;                              // last unique position
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

int main() {
    vector<int> v = {1, 1, 2, 2, 2, 3, 4, 4};
    int len = remove_duplicates(v);
    for (int i = 0; i < len; i++) cout << v[i] << " ";
    cout << "\n";                              // 1 2 3 4
    return 0;
}

fast scans everything; slow marks where the next unique value belongs. O(n) time, O(1) space, and the array is modified in place - which is the part the question is really testing.

Practice, in this order

1. Valid palindrome, ignoring non-letters.
2. Container with most water.
3. Three sum - sort, fix one element, then two pointers on the rest.
4. Sort colours, the Dutch national flag problem, with three pointers.