Two Pointers

The idea

Instead of checking all O(n²) pairs (i, j), move two indices through the data so that each step safely rules out many pairs at once. The total movement is O(n).

There are three shapes:

Why it's correct: the elimination argument

For a sorted array and target sum, at pointers l < r:

• If a[l] + a[r] < target: every pair (l, j) with j ≤ r is also too small (since a[j] ≤ a[r]). So l can never be part of the answer → l += 1.
• If a[l] + a[r] > target: symmetric → r -= 1.

Each step discards an entire row or column of the pair matrix. Being able to state why a pointer can move is what separates a correct two-pointer solution from a lucky one.

Template 1: Opposite ends

def two_sum_sorted(a, target):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return [l, r]
        if s < target:
            l += 1
        else:
            r -= 1
    return []

vector<int> twoSumSorted(vector<int>& a, int target) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == target) return {l, r};
        if (s < target) l++; else r--;
    }
    return {};
}

Counting pairs with sum < target

When the condition holds for (l, r), it holds for (l, l+1) … (l, r) too — count them all at once.

def count_pairs_less(a, target):
    a.sort()
    l, r, count = 0, len(a) - 1, 0
    while l < r:
        if a[l] + a[r] < target:
            count += r - l       # pairs (l, l+1..r)
            l += 1
        else:
            r -= 1
    return count

k-Sum: fix some, two-pointer the rest

def three_sum(nums):
    nums.sort()
    res, n = [], len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                       # skip duplicate anchors
        if nums[i] > 0:
            break                          # smallest is positive → no zero sum
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1                 # skip duplicate seconds
    return res

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i + 2 < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        if (nums[i] > 0) break;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (s < 0) l++;
            else if (s > 0) r--;
            else {
                res.push_back({nums[i], nums[l], nums[r]});
                l++; r--;
                while (l < r && nums[l] == nums[l - 1]) l++;
            }
        }
    }
    return res;
}

k-Sum in general is O(n^(k−1)): sort, fix k−2 indices with loops (or recursion), two-pointer the last two.

Greedy on the shorter side: Container With Most Water

def max_area(h):
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        best = max(best, (r - l) * min(h[l], h[r]))
        if h[l] < h[r]:
            l += 1          # the shorter wall limits the area; moving the taller can't help
        else:
            r -= 1
    return best

Trapping Rain Water in O(1) space

def trap(h):
    l, r = 0, len(h) - 1
    left_max = right_max = water = 0
    while l < r:
        if h[l] < h[r]:
            left_max = max(left_max, h[l])
            water += left_max - h[l]     # right side has something taller, so left_max is the limit
            l += 1
        else:
            right_max = max(right_max, h[r])
            water += right_max - h[r]
            r -= 1
    return water

Template 2: Same direction (read/write)

read scans every element; write marks where the next kept element goes. Everything before write is the answer so far.

def remove_duplicates(nums):             # sorted input, keep one of each
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int write = 1;
    for (int read = 1; read < (int)nums.size(); read++)
        if (nums[read] != nums[write - 1]) nums[write++] = nums[read];
    return write;
}

Template 3: Two sequences

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

def intersect_sorted(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return out

The same shape merges sorted arrays, compares version strings, and checks backspace string compare (scan both from the end with skip counters).

Two pointers vs. other techniques

Common mistakes

• Using l <= r when a pair needs two distinct elements (should be l < r).
• Forgetting to skip duplicates → duplicate triplets in the output.
• Moving the wrong pointer — always justify the move with the elimination argument.
• Sorting when the problem asks for original indices (keep (value, index) pairs).
• Overflow in C++ when summing four ints (4Sum): cast to long long.