Two Pointers "Explained (C++)

Introduction

The 'Two Pointers' "is a common technique used to solve coding problems that involve iterating through an array (or a linked list) with two pointers. These two pointers usually move at different speeds or from different directions to find a solution. This "is very efficient for solving problems with sorted arrays.

When to Use the Two Pointers Pattern

Here are some scenarios where the Two Pointers "is useful:

• Problems involving sorted arrays.
• Problems where you need to find pairs or triplets that satisfy a certain condition.
• Problems where you need to compare elements in an array.
• Problems where you need to reverse parts of an array.

Basic Template

Here's a general structure for implementing the Two Pointers pattern:

#include <iostream>
#include <vector>

using namespace std;

void solveProblem(vector<int>& arr) {
    // Initialize the two pointers.
    int left = 0;
    int right = arr.size() - 1;

    // Iterate until the pointers meet or cross each other.
    while (left < right) {
        // Do some operation with the elements at left and right.
        if (arr[left] + arr[right] == targetValue) { // Example condition
            // Solution found!
            cout << "Found a pair: " << arr[left] << ", " << arr[right] << endl;
            left++;
            right--;
        } else if (arr[left] + arr[right] < targetValue) {
            left++; // Move left pointer to the right
        } else {
            right--; // Move right pointer to the left
        }
        // Move the pointers. The movement depends on the problem.
        // left++;  // Example: Move left pointer one step to the right.
        // right--; // Example: Move right pointer one step to the left.
    }
}

int main() {
  vector<int> numbers = {1, 2, 3, 4, 5, 6, 7};
  int targetValue = 9;
  solveProblem(numbers);
  return 0;
}

Explanation:

1. Initialization: Initialize two pointers, left and right. left usually starts at the beginning of the array (index 0), and right usually starts at the end of the array (index size() - 1).
2. Iteration: Use a while loop to iterate as long as left is less than right. This ensures that you're considering all possible pairs of elements.
3. Operation: Inside the loop, perform the necessary operation with the elements at arr[left] and arr[right]. This could involve comparing them, adding them, or checking for a specific condition.
4. Movement: Move the pointers based on the problem's requirements. The most common movements are:
   • left++: Move the left pointer one position to the right.
   • right--: Move the right pointer one position to the left.
5. Termination: The loop continues until the two pointers meet (left == right) or cross each other (left > right). At this point, you have either found the solution or determined that no solution exists.

Example Problem: Two Sum (Sorted Array)

Problem: Given a sorted array of integers, find two numbers that add up to a specific target value.

C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

pair<int, int> findTwoSum(const 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) {
            return {left, right}; // Return the *indices* of the two numbers.
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {-1, -1}; // Return {-1, -1} if no such pair exists.
}

int main() {
    vector<int> numbers = {2, 7, 11, 15};
    int targetSum = 9;

    pair<int, int> result = findTwoSum(numbers, targetSum);

    if (result.first != -1) {
        cout << "Found two numbers at indices " << result.first << " and "
             << result.second << " that add up to " << targetSum << endl;
    } else {
        cout << "No two numbers found that add up to " << targetSum << endl;
    }
    return 0;
}

Explanation:

1. Initialization: left starts at 0, and right starts at arr.size() - 1.
2. Iteration: The while loop continues as long as left < right.
3. Sum Calculation: Calculate the sum of the elements at the left and right pointers.
4. Comparison:
   • If the sum equals the target, we found the pair. Return the indices.
   • If the sum is less than the target, we need a larger sum, so we increment left to move to a larger number.
   • If the sum is greater than the target, we need a smaller sum, so we decrement right to move to a smaller number.
5. No Solution: If the loop finishes without finding a pair, return {-1, -1}.

Key Points

• The Two Pointers "is very efficient, often solving problems in O(n) time, where n is the size of the array.
• This "is particularly useful for sorted arrays because the ordering helps you decide how to move the pointers.
• Remember that the pointer movement logic is crucial and depends on the specific problem.