← Index

Techniques & Patterns

Two Pointers

Walk two positions through data instead of nesting loops.

What it is

Instead of comparing every pair with a nested loop (O(n²)), keep two pointers moving through the structure — often from opposite ends toward the middle, or one fast/one slow — and let their relationship do the work. It turns a lot of 'check every combination' problems into a single O(n) pass.

Real-world examples

• Two people meeting in the middle of a long hallway to hand off boxes faster than one person walking it alone.
• Checking if a word is a palindrome by comparing the first and last letters and working inward, instead of comparing every letter to every other letter.

Where you've probably used this already

• Form validation matching opening/closing brackets, quotes, or tags from both ends inward.
• Merging or diffing two already-sorted lists (e.g. reconciling two paginated, sorted API responses).
• Removing duplicates or filtering in-place on a sorted array without allocating a second array (fast/slow pointer variant).

Complexity

Code

// Two Pointers — walk two positions through a structure (often from
// both ends, or one fast/one slow) instead of nesting loops.
// Turns a lot of O(n^2) "check every pair" problems into O(n).

// --- Example 1: pair sum in a SORTED array ---
function pairSumSorted(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;

  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [sorted[left], sorted[right]];
    if (sum < target) left++;   // need a bigger sum, move left pointer up
    else right--;                // need a smaller sum, move right pointer down
  }
  return null;
}

// --- Example 2: reverse an array in place ---
function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

// --- Example 3: is this string a palindrome? ---
function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  return true;
}

// --- Example 4: remove duplicates from a sorted array in place (fast/slow) ---
function removeDuplicates(sorted) {
  if (sorted.length === 0) return 0;
  let slow = 0; // last known-unique position
  for (let fast = 1; fast < sorted.length; fast++) {
    if (sorted[fast] !== sorted[slow]) {
      slow++;
      sorted[slow] = sorted[fast];
    }
  }
  return slow + 1; // new length
}

// --- Example Usage ---
console.log("pairSumSorted([1,3,4,7,9], 11):", pairSumSorted([1, 3, 4, 7, 9], 11)); // [4,7]
console.log("reverseInPlace([1,2,3,4]):", reverseInPlace([1, 2, 3, 4])); // [4,3,2,1]
console.log("isPalindrome('racecar'):", isPalindrome("racecar")); // true
const dups = [1, 1, 2, 2, 3];
console.log("removeDuplicates length:", removeDuplicates(dups), dups.slice(0, 3)); // 3 [1,2,3]

// You reach for this pattern any time you're comparing/merging from
// both ends: form validation (matching brackets/quotes), diffing two
// sorted lists, or trimming whitespace from both ends of a string manually.