Two Pointers Pattern (Converging & Symmetrical)

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. The Converging Pointers Technique

The Two Pointers Pattern uses two index pointers that start at opposite ends of a sequence (left = 0 and right = arr.length - 1) and move toward each other until they meet.

2. Why It Matters

Instead of checking all pairs with nested loops in $O(N^2)$ quadratic time, two pointers reduce the search space to a single linear pass in $O(N)$ time and $O(1)$ space.

3. Classic Problem: Two Sum in a Sorted Array

Given an array sorted in ascending order, find two numbers that sum to a given target:

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

  while (left < right) {
    const currentSum = numbers[left] + numbers[right];

    if (currentSum === target) {
      return [left, right]; // Found exact pair!
    } else if (currentSum < target) {
      left++; // Sum is too small, move left pointer rightward to increase sum
    } else {
      right--; // Sum is too large, move right pointer leftward to decrease sum
    }
  }

  return []; // No pair found
}

// Example Execution
console.log(twoSumSorted([2, 7, 11, 15], 9));   // Output: [0, 1]
console.log(twoSumSorted([1, 3, 4, 8, 10], 12)); // Output: [2, 3] (4 + 8)

4. Visual Pointer Movement

Array:   [ 2 ,  7 , 11 , 15 ]   Target: 9
           ▲              ▲
         left           right   Sum: 2 + 15 = 17 (> 9) -> right--

Array:   [ 2 ,  7 , 11 , 15 ]
           ▲       ▲
         left    right          Sum: 2 + 11 = 13 (> 9) -> right--

Array:   [ 2 ,  7 , 11 , 15 ]
           ▲    ▲
         left  right            Sum: 2 + 7 = 9 (Match!) -> Return [0, 1]

5. Common Mistakes

• Applying to Unsorted Arrays: The converging two-pointer sum technique ONLY works on sorted arrays. On unsorted inputs, sorting first takes $O(N log N)$ or you should use a Hash Map in $O(N)$.
• Loop Condition Off-By-One: Using while (left <= right) for pair sum problems can cause an element to be added to itself if left === right. Use left < right for distinct pairs.

6. Next Steps

Use converging pointers on sorted arrays and palindromes. Next, let's explore Fast and Slow Pointers for Cycle Detection!