Two Pointers

When to use: pair problems on sorted arrays
  - Two Sum (sorted input)
  - Container With Most Water
  - 3Sum (fix one, two-pointer the rest)
 
arr = [-3, -1, 2, 4, 7, 9]  target = 6
       ↑L                ↑R
 
Step 1: -3 + 9 = 6 ✓  FOUND at [0, 5]
 
arr = [-3, -1, 2, 4, 7, 9]  target = 3
       ↑L                ↑R
 
Step 1: -3 + 9 = 6 > 3  → R--
Step 2: -3 + 7 = 4 > 3  → R--
Step 3: -3 + 4 = 1 < 3  → L++
Step 4: -1 + 4 = 3 ✓  FOUND at [1, 3]

// Two Sum on sorted array, O(n) time, O(1) space
function twoSumSorted(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    if (sum < target)  left++;   // need more
    else               right--;  // need less
  }
  return [];
}
 
// 3Sum: sort, then for each element fix it and two-pointer the rest
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicates
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left+1]) left++;   // skip dups
        while (left < right && nums[right] === nums[right-1]) right--;
        left++; right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}

When to use:
  - Remove duplicates in-place
  - Move zeros to end
  - Partition array around a value
  - Linked list cycle detection
 
Remove duplicates from sorted array [1,1,2,3,3,4]:
 
write=0, read=0
read=0: arr[0]=1 → write 1 at write=0, write++   → [1,1,2,3,3,4] write=1
read=1: arr[1]=1 = arr[write-1] → SKIP (duplicate)
read=2: arr[2]=2 ≠ arr[write-1] → write 2 at write=1, write++  → [1,2,2,3,3,4] write=2
read=3: arr[3]=3 ≠ arr[write-1] → write 3 at write=2, write++  → [1,2,3,3,3,4] write=3
read=4: arr[4]=3 = arr[write-1] → SKIP
read=5: arr[5]=4 ≠ arr[write-1] → write 4 at write=3, write++  → [1,2,3,4,3,4] write=4
 
Result: first 4 elements are [1,2,3,4] ✓

// Remove duplicates in-place, O(n) time, O(1) space
function removeDuplicates(nums) {
  if (!nums.length) return 0;
  let write = 1; // next position to write unique value
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {
      nums[write++] = nums[read];
    }
  }
  return write; // new length
}
 
// Move zeros to end, preserve order of non-zeros
function moveZeroes(nums) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) nums[write++] = nums[read]; // write non-zeros
  }
  while (write < nums.length) nums[write++] = 0; // fill remaining with 0
}

Find middle of list: 1 → 2 → 3 → 4 → 5
 
slow: 1 → 2 → 3      (moves 1 step per iteration)
fast: 1 → 3 → 5      (moves 2 steps per iteration)
 
When fast = 5 (end), slow = 3 (middle) ✓

function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}
 
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// Longest palindromic substring
function longestPalindrome(s) {
  let start = 0, maxLen = 1;
 
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l + 1 > maxLen) { start = l; maxLen = r - l + 1; }
      l--; r++;
    }
  }
 
  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd-length palindromes
    expand(i, i + 1); // even-length palindromes
  }
  return s.slice(start, start + maxLen);
}