What is the two pointer algorithm?

What is the two pointer algorithm?

Two pointer technique is used to solve this problem in O(n) time complexity and O(1) space complexity

For example lets suppose you have a sorted array and you want to find the sum of two elements such that they are equal to given number

Example

//  Input: numbers = [2,7,11,15], target = 9
//  Output: [1,2]

Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Implementation of two pointer

function twoSum(numbers: number[], target: number): number[] {
    let i = 0;
    let j = numbers.length - 1;
    while (i < j) {
        let sum = numbers[i] + numbers[j];
        if (sum === target) {
            return [i + 1, j + 1];
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }
    return [-1, -1];
}

Let’s understand the algorithm step by step

• We have two pointers i and j and we are moving i pointer to the right and j pointer to the left
• If the sum of the elements at i and j is equal to the target then we return the indices of the elements
• If the sum of the elements at i and j is less than the target then we move the i pointer to the right
• If the sum of the elements at i and j is greater than the target then we move the j pointer to the left
• If the sum of the elements at i and j is not equal to the target then we return [-1,-1]