• Introduction
• Different Types of Two Pointers
  • Two pointers moving in opposite directions
  • Two pointers moving at different speeds
  • Two pointers on different arrays
• Applications of the Two Pointers Technique
• Run C Programming Online Compiler

¶Introduction

The two-pointer technique is a common algorithmic approach used to solve problems involving arrays, linked lists, and strings. It involves using two pointers to traverse through the data structure efficiently. This method is particularly useful when dealing with sorted arrays or linked lists, as it can often reduce time complexity compared to brute force approaches.

¶Different Types of Two Pointers

¶Two pointers moving in opposite directions

Useful for problems like finding pairs with a specific condition in a sorted array. let’s consider the following problem,

Given a sorted array of integers and a target sum, find two numbers in the array that add up to the target sum.

Solution:
We can solve this problem using two pointers method where two pointers will move towards opposite directions.

1. Place one pointer (left) at the beginning of the array and the other pointer (right) at the end.
2. Calculate the sum of the elements at the left and right pointers.
3. If the sum equals the target, return the indices.
4. If the sum is less than the target, move the left pointer to the right to increase the sum.
5. If the sum is greater than the target, move the right pointer to the left to decrease the sum.
6. Repeat the sum calculation and condition checking until the left pointer is no longer less than the right pointer.

Implementation in C++:

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

pair<int, int> findTwoSum(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

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

int main() {
    vector<int> nums = {1, 2, 3, 4, 6, 8, 11, 15};
    int target = 10;

    pair<int, int> result = findTwoSum(nums, target);

    if (result.first != -1) {
        cout << "Pair found at indices: " << result.first << " and " << result.second << endl;
    } else {
        cout << "No pair found." << endl;
    }

    return 0;
}

Time and Space Complexity
Time complexity: O(n)
Space complexity: O(n)

¶Two pointers moving at different speeds

Useful for problems like finding sub-arrays with a specific condition. let’s consider the following problem,

Given an array of integers, find the length of the longest sub-array that contains no duplicate numbers.

Solution:
we can use the sliding window and two pointers technique along with a map data-structure.

1. Use two pointers, left and right, to represent the current window.
2. Use an map to store the frequency of elements in the current window.
3. Iterate with the right pointer from the start to the end of the array. For each element at right, check if it is already in the map.
4. If it is not in the map, add it and update the maximum length.
5. If it is in the map, shrink the window from the left until the element at right can be added without duplicates.
6. Continuously update the maxLength variable with the size of the current window if it is larger than the previously recorded maximum length.

Implementation in C++:

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

int longestUniqueSubarray(const vector<int>& nums) {
    map<int, int> elementCount;
    int left = 0, right = 0, maxLength = 0;

    while (right < nums.size())
    {
        while (elementCount[nums[right]] > 0)
        {
            elementCount[nums[left]]--;
            ++left;
        }
        elementCount[nums[right]]++;
        maxLength = max(maxLength, right - left + 1);
        ++right;
    }
    return maxLength;
}

int main() {
    vector<int> nums = {2, 3, 4, 5, 2, 7, 4, 6, 8, 9};
    cout << "The length of the longest subarray without duplicate numbers is: " 
         << longestUniqueSubarray(nums) << endl;

    return 0;
}

Time and Space Complexity
Time complexity: O(nlog(n))
Space complexity: O(n)

¶Two pointers on different arrays

Useful for problems like merging two sorted arrays on a condition. let’s consider the following problem,

Given two sorted arrays, merge them into a single sorted array.

Solution:
To merge two sorted arrays, we can use a two-pointer technique to efficiently combine the elements in sorted order. The idea is to traverse both arrays simultaneously, comparing elements and placing the smaller one into the result array.

1. Use two pointers, i and j, to traverse the first and second arrays, respectively.
2. Compare the current elements of both arrays (pointed to by i and j).
3. Place the smaller element into the result array and move the corresponding pointer to the next element.
4. If there are remaining elements in one array, append all the elements of the other array to the result array.
5. Repeat this process until both of the arrays are fully traversed.

Implementation in C++:

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

vector<int> mergeSortedArrays(const vector<int>& arr1, const vector<int>& arr2) {
    vector<int> mergedArray;
    int i = 0, j = 0;

    // Traverse both arrays
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            mergedArray.push_back(arr1[i]);
            i++;
        } else {
            mergedArray.push_back(arr2[j]);
            j++;
        }
    }

    // Add remaining elements of arr1
    while (i < arr1.size()) {
        mergedArray.push_back(arr1[i]);
        i++;
    }

    // Add remaining elements of arr2
    while (j < arr2.size()) {
        mergedArray.push_back(arr2[j]);
        j++;
    }

    return mergedArray;
}

int main() {
    vector<int> arr1 = {1, 3, 5, 7};
    vector<int> arr2 = {2, 4, 6, 8};

    vector<int> result = mergeSortedArrays(arr1, arr2);

    cout << "Merged array: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Time and Space Complexity
Time complexity: O(n + m)
Space complexity: O(n + m)

¶Applications of the Two Pointers Technique

1. Cycle Detection: Hare and Tortoise Algorithm : Detects cycles in linked lists. One pointer (tortoise) moves one node at a time, while the other (hare) moves two nodes at a time. If there’s a cycle, they will eventually meet.

2. Array/List Traversal : Iterates through arrays or linked lists efficiently. Often used for finding pairs, triplets, or specific elements with certain conditions.

3. Sorting Algorithms : Used in algorithms like Quick Sort and Merge Sort. Helps partition arrays or merge sorted subarrays.

4. String Manipulation : palindrome checking, finding substrings, anagram checking.

5. Geometric Algorithms : Used in computational geometry problems. Involves operations like finding intersections, calculating distances, and analyzing shapes.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online