Step 4 of 6

Two pointers

On sorted data, two indexes moving toward each other can often replace a nested loop. Each comparison lets you rule out one element for good, so the whole scan is O(n) instead of O(n²).

Here's the idea on a different problem: is a string a palindrome (the same forwards and backwards), ignoring non-letters?

#include <cctype>
#include <iostream>
#include <string>

bool is_palindrome(const std::string& s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (!std::isalpha((unsigned char)s[i])) { i++; continue; }
        if (!std::isalpha((unsigned char)s[j])) { j--; continue; }
        if (std::tolower((unsigned char)s[i]) != std::tolower((unsigned char)s[j])) return false;
        i++;
        j--;
    }
    return true;
}

int main() {
    std::cout << is_palindrome("Never odd or even") << is_palindrome("A man, a plan, a canal: Panama")
              << is_palindrome("two pointers") << "\n";
}

110

Two pointers for a target sum

For "do two numbers in a sorted list add up to target?":

• start with i at the smallest value and j at the largest,
• if v[i] + v[j] is too small, the only way to grow the sum is to move i right (j is already the biggest),
• if it's too big, move j left,
• if it's equal, you've found a pair.

Every step discards one value that can't be part of any answer, so the loop runs at most n times. Stop when i meets j, because the two positions must be different.

Watch the types: target is a long, and two big ints can overflow when added. Add them as long: (long)v[i] + v[j].

Your turn: write bool pair_sum(const std::vector<int>& sorted, long target) that says whether two different positions hold values summing to target.

Previous: lower_bound and upper_bound Next: Prefix sums