Two Pointers pattern

In the world of algorithms and data structures, efficient solutions often rely on clever techniques to manipulate data. One such technique, the "two pointers" approach, is particularly useful for solving a variety of problems. While traditionally associated with languages like C and C++, we can leverage this technique in JavaScript to optimize our code.

What are Two Pointers?

The "two pointers" technique involves using two pointers (or indices) to traverse an array or sequence of data. These pointers typically start at different ends or positions within the array and move towards each other, allowing us to efficiently solve problems involving searching, sorting, or manipulating arrays.

Why Use Two Pointers?

The primary benefit of the two pointers approach is its efficiency. By utilizing two pointers, we can often achieve linear or linearithmic time complexity (O(n) or O(n log n)), which is much better than quadratic time (O(n^2)) that can arise with nested loops.

Patterns

Let's explore some common patterns where the two pointers technique shines in JavaScript:

1. Two Sum Problem

Given an array of integers nums and an integer target target, return the indices of the two numbers such that they add up to target.

function twoSum(nums, target) {
    let left = 0;
    let right = nums.length - 1;

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

    return [];
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));  // Output: [0, 1]

2. Reverse a String in Place

Given a character array s, reverse the order of characters in-place.

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

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

    return s;
}

const str = ['h', 'e', 'l', 'l', 'o'];
console.log(reverseString(str));  // Output: ['o', 'l', 'l', 'e', 'h']

3. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length.

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

const nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
console.log(removeDuplicates(nums));  // Output: 5
console.log(nums.slice(0, 5));  // Output: [0, 1, 2, 3, 4]

Conclusion

The "two pointers" technique is a powerful tool in the arsenal of a JavaScript developer when dealing with arrays and sequences. By using two pointers intelligently, we can often achieve efficient and elegant solutions to various algorithmic problems. These patterns not only optimize code but also improve readability and maintainability.

Next time you encounter a problem involving arrays, consider whether the "two pointers" technique could help you arrive at a more efficient solution in your JavaScript code.

Happy coding!