24-Mar-2025

Two pointers is a common algorithmic technique used to solve problems involving arrays or linked lists. It leverages the idea of using two pointers (indices or iterators) to traverse the data structure in a coordinated manner, often improving efficiency compared to brute-force approaches.

There are several variations of the two-pointer technique, each suited to particular problem types:

1. Opposite Ends (Meeting in the Middle):

This approach is useful when searching for pairs or subarrays that satisfy a specific condition. One pointer starts at the beginning of the data structure, and the other starts at the end. They move towards each other, adjusting their positions based on the condition being checked.

Example: Find two numbers in a sorted array that sum to a target value.

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

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

  return null; // No pair found
}


const sortedArray = [2, 7, 11, 15];
const targetValue = 18;
const result = findSumPair(sortedArray, targetValue);

if (result) {
    console.log(`Pair found at indices: ${result}`);
}
else {
    console.log("Pair not found")
}

2. Same Direction (Sliding Window):

This variation is commonly used for problems involving subarrays or substrings of a specific length or property. One pointer marks the beginning of the window, and the other marks the end. The window “slides” through the data structure, maintaining a certain condition.

Example: Find the maximum sum of a subarray of size k.

function maxSubarraySum(arr, k) {
  if (k > arr.length || k <= 0) return 0;

  let maxSum = 0;
  let currentSum = 0;

  // Calculate initial window sum
  for (let i = 0; i < k; i++) {
    currentSum += arr[i];
  }
  maxSum = currentSum;

  // Slide the window
  for (let i = k; i < arr.length; i++) {
    currentSum = currentSum + arr[i] - arr[i - k]; // Efficiently update the sum
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}


const array = [1, 4, 2, 10, 23, 3, 1, 0, 20];
const k = 4;
const maxSum = maxSubarraySum(array, k);
console.log("Maximum subarray sum:", maxSum);

3. Fast and Slow Pointers (Hare and Tortoise):

This technique is often used to detect cycles in linked lists or to find elements at specific positions (e.g., the middle element). The fast pointer moves two steps at a time, while the slow pointer moves one step at a time.

By strategically using these variations, you can optimize solutions to many array and linked list problems, reducing time complexity from O(n^2) to O(n) in many cases. Two pointers is a powerful tool in your DSA problem-solving arsenal.