Implementing Two Pointers in C++

Setting Up the Pointers

In C++, the two-pointer technique doesn't involve actual memory pointers in the int* sense. Instead, we use integer variables that act as indices into an array or a std::vector. The setup is straightforward. For an array or vector of size n, we initialize two integer variables, typically named left and right or slow and fast.

The most common starting positions are with one pointer at the beginning of the array and the other at the end, or with both pointers at the beginning.

#include <vector>

void twoPointerSetup(const std::vector<int>& arr) {
    // Common setup for pointers moving towards each other
    int left = 0;
    int right = arr.size() - 1;

    // Common setup for pointers moving in the same direction
    int slow = 0;
    int fast = 0;
}

Iterative Patterns

The power of this technique comes from how we move the pointers through the data. There are two primary patterns for iterating.

1. Pointers Moving Towards Each Other This pattern is often used on sorted arrays. We start one pointer at the beginning (left) and the other at the end (right). In each step of a loop, we evaluate the elements at these pointers and then move one of them closer to the other. The loop continues until the pointers meet or cross.

2. Pointers Moving in the Same Direction Also known as the "fast and slow" or "sliding window" pattern. Both pointers start at or near the beginning of the array. The fast pointer moves ahead to explore the array, while the slow pointer maintains a certain condition or marks the beginning of a sub-array. This is useful for problems involving finding subarrays or removing duplicates.

Example: Find a Pair with a Given Sum

Let's apply the first pattern to a classic problem. Given a sorted array of integers and a target sum, we need to find if there's a pair of numbers in the array that adds up to that target.

A brute-force approach would use nested loops, resulting in $O(n^2)$ time complexity. With two pointers, we can solve it in $O(n)$ time.

The logic is simple. We start with left at the first element and right at the last. We calculate their sum.

If the sum is equal to the target, we've found our pair.
If the sum is less than the target, we need a larger value. Since the array is sorted, we move the left pointer one step to the right.
If the sum is greater than the target, we need a smaller value. We move the right pointer one step to the left.

We repeat this process until the left and right pointers cross each other. If they cross, it means no such pair exists.

#include <iostream>
#include <vector>
#include <utility> // For std::pair

// Function to find a pair with a given sum in a sorted vector
std::pair<int, int> findSumPair(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        int currentSum = arr[left] + arr[right];

        if (currentSum == target) {
            // Found the pair
            return {arr[left], arr[right]};
        } else if (currentSum < target) {
            // Sum is too small, need a larger number
            left++;
        } else { // currentSum > target
            // Sum is too large, need a smaller number
            right--;
        }
    }

    // Return a pair indicating failure if no pair is found
    return {-1, -1};
}

int main() {
    std::vector<int> numbers = {2, 4, 6, 8, 10, 12};
    int targetSum = 16;
    std::pair<int, int> result = findSumPair(numbers, targetSum);

    if (result.first != -1) {
        std::cout << "Pair found: " << result.first << ", " << result.second << std::endl;
    } else {
        std::cout << "No pair found with the given sum." << std::endl;
    }

    return 0;
}

Avoiding Pitfalls

When implementing the two-pointer technique, it's crucial to handle the loop condition and pointer updates correctly. A common mistake is using while (left <= right) when it should be while (left < right). This can lead to processing the same element twice or causing an infinite loop if the pointers aren't updated correctly inside the loop.

Always consider edge cases:

Empty array: The code should handle an input array with zero elements gracefully. arr.size() - 1 on an empty vector can cause issues. A check at the beginning of the function is good practice.
Array with one element: The condition while (left < right) naturally handles this, as the loop will not execute.
No solution found: Your function should have a clear way to signal that the desired condition was not met, like returning a special value or an empty container.

Quiz Questions 1/5

In the context of the C++ two-pointer technique, what are the "pointers" typically?

Quiz Questions 2/5

When finding a pair of numbers that sum to a target in a sorted array, you have left and right pointers. If the current sum arr[left] + arr[right] is greater than the target, what is the correct next move?

With these patterns, you can start applying the two-pointer technique to a variety of problems.

Mastering the Double Pointer Algorithm in C++