Introduction to the Two-Pointer Technique in C++

Introduction

Welcome to this unit's coding session! We're going to take a deep dive into an exciting technique — the two-pointer technique . This technique is a crucial skill for enhancing your algorithmic problem-solving abilities, especially when dealing with arrays. In this unit, we'll apply this technique to a problem that involves an array of integers and a target value. Let's get started!

Task Statement

Envision the problem at hand: we've been given an array of distinct integers and a target value. The task is to find all pairs of integers from the given array that sum up to the target value using the two-pointer technique. The function find_pairs should take this array of integers and a target value as parameters. It should return a vector containing pairs of numbers, sorted in ascending order by the first element of each pair. If no pairs satisfy this requirement, the function should return an empty vector. Consider, for instance, an example in which you're given an array, numbers = {1, 3, 5, 2, 8, -2}, and target = 6. In this case, the function should return {{-2, 8}, {1, 5}} because only these pairs from the input array of integers add up to the target value.

The Naive Approach

O(n^2)

The Algorithm

We first sort the array and then apply the two-pointer technique: Two pointers, one at the start (left) and the other at the end (right), are initialized. In each iteration, we calculate the sum of the two numbers pointed to by the two respective pointers. If the sum is equal to the target value, the pair is added to the output vector, and both pointers are moved towards the center. This is because we know there are no other potential pairs with the current values of numbers[left] and numbers[right] (since the numbers are distinct). When the sum is less than the target, we move the left pointer to the right (increasing the value of numbers[left]), and when the sum is greater than the target, we move the right pointer to the left (decreasing the value of numbers[right]). This process continues until the left pointer crosses the right pointer. At this point, all potential pairs have already been identified and added to the return vector.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 3

The most challenging and exciting part is the formation of pairs. We'll run a while loop until the left pointer crosses the right one. In each iteration, if the total equals the target, we'll store the pair and move one step from both ends. If the total is smaller than the target, we'll move one step to the right from the left, seeking a larger value. Conversely, if the total is larger than the target, we'll move one step to the left from the right, seeking a smaller value. Here is how it could be done:

C++

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<std::pair<int, int>> find_pairs(std::vector<int>& numbers, int target) {
    std::sort(numbers.begin(), numbers.end());
    int left = 0;
    int right = numbers.size() - 1;
    std::vector<std::pair<int, int>> pairs;

    while (left < right) {
        int total = numbers[left] + numbers[right];

        if (total == target) {
            pairs.push_back({numbers[left], numbers[right]});
            left++;
            right--;
        } else if (total < target) {
            left++;
        } else {
            right--;
        }
    }
    return pairs;
}

int main() {
    std::vector<int> numbers = {1, 3, 5, 2, 8, -2};
    std::vector<std::pair<int, int>> result = find_pairs(numbers, 6);
    for (std::pair<int, int> elm : result) {
        std::cout << elm.first << ' ' << elm.second << std::endl;
    }
    return 0;
}

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<std::pair<int, int>> find_pairs(std::vector<int>& numbers, int target) {
    std::sort(numbers.begin(), numbers.end());
    int left = 0;
    int right = numbers.size() - 1;
    std::vector<std::pair<int, int>> pairs;

    while (left < right) {
        int total = numbers[left] + numbers[right];

        if (total == target) {
            pairs.push_back({numbers[left], numbers[right]});
            left++;
            right--;
        } else if (total < target) {
            left++;
        } else {
            right--;
        }
    }
    return pairs;
}

int main() {
    std::vector<int> numbers = {1, 3, 5, 2, 8, -2};
    std::vector<std::pair<int, int>> result = find_pairs(numbers, 6);
    for (std::pair<int, int> elm : result) {
        std::cout << elm.first << ' ' << elm.second << std::endl;
    }
    return 0;
}

Introduction

Task Statement

The Naive Approach

The Algorithm

Join the 1M+ learners on CodeSignal

Complexity Analysis

Solution Building: Step 1

Solution Building: Step 2

Solution Building: Step 3

Lesson Summary