March 4, 2025

Two Pointers

In the realm of algorithm design, the 2 Pointers Technique stands out as a powerful and versatile approach to solve a variety of problems. From array manipulation to string processing, this method helps optimize both time and space complexity compared to more naive solutions. Whether you’re preparing for coding interviews or refining your problem-solving skills, understanding this technique is essential.

What Is the 2 Pointers Technique?

At its core, the 2 Pointers Technique involves the use of two indices (or pointers) that traverse a data structure — such as an array, string, or linked list — often from different ends or at different speeds. The strategy is to simultaneously examine elements in a way that reduces redundant work and cuts down on the number of iterations needed.

Common Variations

How It Works

The strength of the technique lies in its simplicity and efficiency:

A clear example of this technique is its application in finding two numbers in a sorted array that add up to a given target sum. With one pointer at the start and one at the end, you can efficiently zero in on the correct pair without needing to check every possible combination.

Example Applications

This method has found its way into several classic algorithmic challenges:

1. Finding Pairs with a Given Sum

Given a sorted array, find two numbers that sum up to a given target.

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

  while (left < right) {
    let sum = arr[left] + arr[right];

    if (sum === target) {
      return [arr[left], arr[right]]; // Found the pair
    } else if (sum < target) {
      left++; // Move left pointer to increase sum
    } else {
      right--; // Move right pointer to decrease sum
    }
  }

  return []; // No valid pair found
}

// Example usage:
console.log(twoSumSorted([1, 2, 3, 4, 6], 6)); // Output: [2, 4]

Efficiency

2. Merging Sorted Arrays

Given two sorted arrays, merge them into a single sorted array in O(n + m) time.

function mergeSortedArrays(arr1, arr2) {
  let i = 0,
    j = 0;
  let mergedArray = [];

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      mergedArray.push(arr1[i]);
      i++; // Move pointer in arr1
    } else {
      mergedArray.push(arr2[j]);
      j++; // Move pointer in arr2
    }
  }

  // Add remaining elements from arr1 (if any)
  while (i < arr1.length) {
    mergedArray.push(arr1[i]);
    i++;
  }

  // Add remaining elements from arr2 (if any)
  while (j < arr2.length) {
    mergedArray.push(arr2[j]);
    j++;
  }

  return mergedArray;
}

// Example usage:
console.log(mergeSortedArrays([1, 3, 5, 7], [2, 4, 6, 8]));
// Output: [1, 2, 3, 4, 5, 6, 7, 8]

Efficiency

3. Removing Duplicates

When dealing with a sorted array, we can remove duplicates in O(n) time using the two-pointer technique.

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

  let uniqueIndex = 0; // This pointer keeps track of the unique elements

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[uniqueIndex]) {
      uniqueIndex++;
      arr[uniqueIndex] = arr[i]; // Move unique element to the front
    }
  }

  return arr.slice(0, uniqueIndex + 1); // Return the unique elements
}

// Example usage:
console.log(removeDuplicates([1, 1, 2, 2, 3, 4, 4, 5])); // Output: [1, 2, 3, 4, 5]

Efficiency

4. Detecting Palindromes

A palindrome is a word or phrase that reads the same forward and backward. The two-pointer technique efficiently checks this by comparing characters from both ends.

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) return false; // Mismatch found
    left++;
    right--;
  }

  return true; // It's a palindrome
}

// Example usage:
console.log(isPalindrome("racecar")); // Output: true
console.log(isPalindrome("hello")); // Output: false

Efficiency

5. Cycle Detection in Linked Lists

When working with linked lists, a common problem is detecting whether the list contains a cycle. The slow and fast pointer technique (also called Floyd’s Cycle Detection Algorithm) helps us do this efficiently.

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function hasCycle(head) {
  let slow = head,
    fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next; // Move 1 step
    fast = fast.next.next; // Move 2 steps

    if (slow === fast) return true; // Cycle detected
  }

  return false; // No cycle found
}

// Example usage:
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
node3.next = node1; // Creating a cycle

console.log(hasCycle(node1)); // Output: true

Efficiency