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]