The two pointers technique is an efficient method used to solve problems involving sequences, such as arrays, by using two references to traverse the data structure in one pass. This approach can lead to more elegant and less resource-intensive solutions.

Understanding the two pointers technique

The essence of this technique is to take two references—pointers—to elements in a structure like an array and move them towards or away from each other to analyze or manipulate the elements. The pointers could move from the opposite ends of the array towards the center, or they could start at the same position and move in the same direction, depending on the problem at hand.

When to use two pointers

This technique comes in handy for problems that involve paired elements, like finding a pair that sums up to a particular value or merging two sorted arrays. It's especially useful when you need to minimize space complexity, often allowing for an in-place solution that doesn't require additional data structures.

How two pointers work

Opposite direction movement

Copy text
function findSumPair(arr, sum) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const currentSum = arr[left] + arr[right];
        if (currentSum === sum) {
            return [left, right];
        } else if (currentSum < sum) {
            left++;
        } else {
            right--;
        }
    }

    return null;
}

Same direction movement

Copy text
function maxConsecutiveSum(arr, k) {
    let maxSum = 0;
    let tempSum = 0;
    let start = 0;

    for (let end = 0; end < arr.length; end++) {
        tempSum += arr[end];
        if (end >= k - 1) {
            maxSum = Math.max(maxSum, tempSum);
            tempSum -= arr[start];
            start++;
        }
    }

    return maxSum;
}

Examples of two pointers

Removing duplicates from sorted array

Copy text
function removeDuplicates(arr) {
    if (arr.length === 0) return 0;

    let i = 0;
    for (let j = 1; j < arr.length; j++) {
        if (arr[j] !== arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }

    return i + 1;
}

Reversing a string in place

Copy text
function reverseString(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
}

Benefits and considerations

Using the two pointers technique simplifies code and reduces the need for nested loops, thus cutting down on time complexity. It's important to consider this approach when dealing with linear data structures and when optimizing for efficiency. However, it requires a good understanding of the problem's constraints to apply effectively.