Two Pointer Technique

Real-world analogy

What is it?

The two pointer technique is an algorithmic pattern where two indices traverse an array in a coordinated manner to solve problems efficiently. By strategically moving the pointers based on current values, we can find pairs, remove duplicates, and solve subarray problems in O(n) time, avoiding the O(n^2) brute force approach.

Real-world relevance

Two pointer logic appears in merge operations (merging two sorted lists into one), in text editors (find and replace uses two pointers to scan and write), in traffic management (cars merging from two lanes), and in DNA sequence alignment (comparing two gene sequences simultaneously).

Key points

• What is Two Pointer? — The two pointer technique uses two indices (pointers) that move through an array in a coordinated way. Often one starts at the beginning and one at the end, and they move toward each other. This lets us solve certain problems in O(n) instead of O(n^2).
• Finding a Pair with Target Sum — Given a sorted array and target sum, place left pointer at index 0 and right pointer at index n-1. If arr[left] + arr[right] == target, found it! If sum is too small, move left pointer right (to increase sum). If too big, move right pointer left (to decrease sum).
• Why It Works on Sorted Data — In a sorted array, moving the left pointer right increases the sum, and moving the right pointer left decreases it. This means we can systematically explore all relevant pairs without checking every possible combination. Sorting gives us direction!
• Two Pointers Moving Same Direction — Sometimes both pointers start at the beginning and move right. This is useful for problems like removing duplicates from a sorted array: one pointer (i) scans through, and another (j) marks where to write the next unique element.
• Removing Duplicates Example — Sorted array: [1,1,2,2,3]. Use pointer j=0 for writing position. For each element at pointer i: if arr[i] != arr[j], increment j and copy arr[i] to arr[j]. Result: [1,2,3,...] with j+1 = 3 unique elements.
• Time Complexity Advantage — Without two pointers, finding a pair with a given sum requires two nested loops: O(n^2). With two pointers on sorted data, each pointer moves at most n times, so the total work is O(n). For n = 100,000, that is 100,000 vs 10,000,000,000 operations!
• When to Use Two Pointers — Look for these clues: (1) the array is sorted or can be sorted, (2) you need to find pairs or subarrays satisfying some condition, (3) a brute force solution uses two nested loops. If you see these, two pointers might help!
• Common Variations — Two pointer variations include: (1) opposite ends moving inward (pair sum), (2) same direction with fast/slow pointers (cycle detection, duplicates), (3) sliding window (upcoming topic!). All share the idea of two coordinated indices.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Problem 1: Find pair with target sum in sorted array
    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());

    int left = 0, right = n - 1;
    bool found = false;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << "Pair found: " << arr[left] << " + " << arr[right] << " = " << target << "\n";
            found = true;
            break;
        } else if (sum < target) {
            left++;  // Need bigger sum, move left pointer right
        } else {
            right--; // Need smaller sum, move right pointer left
        }
    }
    if (!found) cout << "No pair found\n";

    // Problem 2: Count unique elements in sorted array
    sort(arr.begin(), arr.end());
    int unique = 1; // First element is always unique
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i - 1]) {
            unique++;
        }
    }
    cout << "Unique elements: " << unique << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. int left = 0, right = n - 1; — we place our two pointers at opposite ends of the sorted array. left starts at the smallest element, right at the largest.
2. 2. int sum = arr[left] + arr[right]; — we calculate the sum of the elements at our two pointers. This is the pair we are currently examining.
3. 3. if (sum == target) — if the sum equals our target, we found a valid pair! We print it and stop searching.
4. 4. else if (sum < target) { left++; } — if the sum is too small, we need a bigger number. Since the array is sorted, moving left forward gives us the next bigger element from the left side.
5. 5. else { right--; } — if the sum is too big, we need a smaller number. Moving right backward gives us the next smaller element from the right side.
6. 6. while (left = right, there are no more valid pairs to check.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target = 12;
    int left = 0, right = arr.size();

    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << arr[left] << " + " << arr[right] << "\n";
            break;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Two Pointer Technique (GeeksforGeeks)
• Two Pointer Algorithm Explained (YouTube)
• Sum of Two Values (CSES)