TWO POINTER TECHNIQUE C++

In this chapter of C++ programs, we will learn about:

two pointer technique c++

INTRODUCTION : The Two Pointers Technique in C++ Algorithms

The two pointers technique is a popular and efficient algorithmic strategy used to solve various problems in computer science, especially in the context of arrays and linked lists. This technique involves using two pointers to iterate through the data structure in order to find a solution with optimal time complexity.

What is two pointer technique?

The two pointers technique involves maintaining two different indices (or pointers) that traverse the array or list in tandem.
These pointers can move towards each other, away from each other, or in the same direction.
The main advantage of this technique is its ability to reduce the time complexity of algorithms from quadratic to linear in many cases.

Common Use Cases of two pointer approach in c++:

Listed below are areas where two pointer approach in c++ can be applied for better result:

Finding pairs in a sorted array that sum to a target value.
Removing duplicates from a sorted array.
Checking if a string is a palindrome.
Merging two sorted arrays.
Partitioning arrays in a specific manner.

Let's explore some of these use cases with example code where two pointer algorithm c++ can be applied.

Example 1: Finding Pairs in a Sorted Array that Sum to a Target Value

Given a sorted array, the goal is to find all pairs of numbers that add up to a given target sum. The two pointers technique allows us to solve this problem efficiently.

CODE:

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

void findPairsWithSum(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << "Pair found: (" << arr[left] << ", " << arr[right] << ")" << endl;
            left++;
            right--;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 10;
    findPairsWithSum(arr, target);
    return 0;
}

OUTPUT:

Pair found: (1, 9)

Pair found: (2, 8)

Pair found: (3, 7)

Pair found: (4, 6)

Example 2: Removing Duplicates from a Sorted Array

In a sorted array, duplicates appear consecutively. Using the two pointers technique, we can remove duplicates in-place.

CODE:

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

int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int j = 0;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] != arr[j]) {
            j++;
            arr[j] = arr[i];
        }
    }
    return j + 1;
}

int main() {
    vector<int> arr = {1, 1, 2, 2, 2, 3, 4, 4, 5};
    int newLength = removeDuplicates(arr);
    cout << "Array after removing duplicates: ";
    for (int i = 0; i < newLength; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

OUTPUT:

Array after removing duplicates: 1 2 3 4 5

Example 3: Checking if a String is a Palindrome

To check if a string is a palindrome, we can use two pointers starting from the beginning and end of the string and moving towards the center.

CODE:

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(const string& str) {
    int left = 0, right = str.length() - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string str = "racecar";
    if (isPalindrome(str)) {
        cout << str << " is a palindrome." << endl;
    } else {
        cout << str << " is not a palindrome." << endl;
    }
    return 0;
}

OUTPUT:

racecar is a palindrome.

The time complexity for all three examples is O(n), making them efficient solutions for their respective problems.

Conclusion:

The two pointers technique is a versatile and efficient approach to solving a variety of problems involving arrays and strings. By leveraging two pointers to traverse the data structure, we can often reduce the time complexity and achieve more optimal solutions.

The examples on two pointer technique c++ provided demonstrate some common use cases, but the technique can be applied to many other problems as well.

This wraps up our session on two pointer approach in c++ or two pointer algorithm c++

CPP Programs

Would you like to see your article here on tutorialsinhand. Join Write4Us program by tutorialsinhand.com

About the Author

kumkum tiwari

Page Views : Published Date : Jul 10,2024

Please Share this page