two-pointer • Intermediate

Two-Pointer Technique: Opposite Ends & In-Place Convergence

Two pointers starting at opposite ends (left = 0, right = N - 1) converge toward the center, eliminating nested loops from O(N^2) down to O(N) by exploiting monotonicity in sorted arrays.

Intuitive Mental Model

The Vice Grips: Two metal clamps move toward each other from the left and right ends of a wooden beam, narrowing down the target location in a single pass.

C / TypeScript ImplementationHardware & Algorithmic Standard

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

  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) {
      return [left + 1, right + 1];
    } else if (sum < target) {
      left++; // Sum is too small, move left pointer right
    } else {
      right--; // Sum is too large, move right pointer left
    }
  }
  return [];
}

Key Architectural Takeaways

•Monotonicity Requirement: Moving left pointer strictly increases sum; moving right pointer strictly decreases sum.
•Space Optimization: Operates with O(1) auxiliary memory without requiring hash maps.
•Classic Applications: Palindrome verification, Container With Most Water, 3Sum, Trapping Rain Water.

Common Coding Mistake

Applying opposite-end two pointers to unsorted arrays without sorting first, breaking the monotonic direction invariant.

Optimal Solution

Ensure the array is sorted before applying directional convergence.

Next: Fast and Slow Pointers (Floyd's Cycle Finding Algorithm)