👆 Two Pointers — JavaScript

Index: Two Pointers Index | Parent: JS Array Index

---

Pattern 1: Opposite Direction (Sorted Array / Palindrome)

// Template
function twoPointersOpposite(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    if (/* condition met */) return result;
    else if (/* need larger */) left++;
    else right--;
  }
  return defaultResult;
}

Pattern 2: Same Direction (Slow/Fast Pointer)

// Template — remove duplicates / in-place filter
function twoPointersSameDir(arr) {
  let slow = 0;
  for (let fast = 0; fast < arr.length; fast++) {
    if (/* keep condition */) {
      arr[slow++] = arr[fast];
    }
  }
  return slow; // new logical length
}

---

Q1. Two Sum — Pair Equals Target (Sorted) [E][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Sorted array + find a pair = Two Pointers (opposite direction). The sorted order is your cheat sheet.

Step 2 — Brute force:

Two nested loops → O(n²). With n=100,000, that's 10 billion checks.

Step 3 — Optimal insight:

Start with widest range (L=0, R=n-1). Sum tells you which direction to narrow:

- Too small → L++ (get a bigger left value)

- Too big → R-- (get a smaller right value)

- Match → done

Step 4 — Unsorted variant:

Use a Map. For each number, check if (target - num) was seen before.

Step 5 — Edge cases:

- Multiple pairs: return first found or all of them

- No pair: return [] after loop

Way of Thinking: Sum < target → move left pointer right to increase sum. Sum > target → move right pointer left.

function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target)    return [left, right];
    else if (sum < target) left++;
    else                   right--;
  }
  return [];
}

// Unsorted — use Map O(n)
function twoSumUnsorted(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([2,7,11,15], 9)); // [0,1]

---

Q2. Three Sum — All Triplets Summing to 0 [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Reduce the 3-element problem to 2-element two-sum by fixing one element with an outer loop.

Step 2 — Why sorting is key:

Sorted array lets you: (1) use two pointers for the inner loop, and (2) easily skip duplicates.

Step 3 — Algorithm:

1. Sort the array

2. For each i: if nums[i] === nums[i-1]: skip (duplicate)

3. Two pointers L=i+1, R=n-1, find pair summing to -nums[i]

4. On match: add triplet, skip duplicate L and R values

Step 4 — Edge cases:

- All same (e.g. [0,0,0]): single valid triplet

- No valid triplets: return empty array

Way of Thinking: Sort → fix one element → use two pointers on the rest. Skip duplicates to avoid repeated triplets.

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 duplicate i

    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++;
        while (left < right && nums[right] === nums[right-1]) right--;
        left++;
        right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}

console.log(threeSum([-1,0,1,2,-1,-4]));
// [[-1,-1,2],[-1,0,1]]

---

Q3. Remove Duplicates In-Place [E][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Modify array in-place without extra space = slow/fast pointer (same direction).

Step 2 — Brute force:

Copy unique elements to new array → O(n) space. Problem demands O(1).

Step 3 — Optimal insight:

slow tracks the next write position. fast scans ahead. Only write if current element differs from the element before it (to skip duplicates).

Step 4 — Algorithm:

1. slow = 1 (first element is always kept)

2. for fast from 1 to end: if nums[fast] !== nums[fast-1], copy to nums[slow++]

3. Return slow (count of unique elements)

Step 5 — Edge cases:

- Empty array: return 0

- All duplicates: slow stays at 1

Way of Thinking: Slow pointer marks next write position. Fast pointer scans. Write only when different from previous.

function removeDuplicates(nums) {
  if (!nums.length) return 0;
  let slow = 1;
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow++] = nums[fast];
    }
  }
  return slow; // nums[0..slow-1] is the result
}

console.log(removeDuplicates([1,1,2,3,3,4])); // 4 → nums = [1,2,3,4,...]

---

Q4. Container With Most Water [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Maximize area between two lines → two pointers from both ends, shrink toward each other.

Step 2 — Brute force:

Check every pair of lines → O(n²). Too slow for large inputs.

Step 3 — Key insight:

Area = min(height[L], height[R]) × (R - L). Moving the TALLER wall inward never helps (width shrinks and min stays the same or worse). Always move the SHORTER wall inward — it's the only move that could possibly increase the area.

Step 4 — Algorithm:

1. L=0, R=n-1, max=0

2. While L < R: compute area, update max

3. Move pointer of shorter height inward

Step 5 — Edge cases:

- Equal height walls: move either pointer (doesn't matter)

Way of Thinking: Area = min(height[L], height[R]) * (R - L). Always move the shorter wall inward — moving the taller can only decrease width without potentially increasing height.

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let max = 0;

  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    max = Math.max(max, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return max;
}

console.log(maxArea([1,8,6,2,5,4,8,3,7])); // 49

---

Q5. Valid Palindrome [E][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Check symmetry from both ends → classic opposite-direction two pointers.

Step 2 — Brute force:

Reverse the string and compare → O(n) space.

Step 3 — Optimal insight:

Two pointers from both ends, skip non-alphanumeric characters, compare lowercase versions. No need to build cleaned string.

Step 4 — Algorithm:

1. L=0, R=n-1

2. While L < R: skip non-alphanumeric chars on each side

3. Compare lowercase; if mismatch → false; else L++, R--

Step 5 — Edge cases:

- Empty string: true (trivially palindrome)

- All punctuation: true

Way of Thinking: Clean the string first, then compare from both ends. Move inward while they match.

function isPalindrome(s) {
  // Keep only alphanumeric, lowercase
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let left = 0, right = clean.length - 1;
  while (left < right) {
    if (clean[left] !== clean[right]) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

---

Q6. Trap Rainwater [H][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Water trapped at any index = min(maxLeft, maxRight) - height[i]. Signals two-pointer approach.

Step 2 — Brute force:

For each position, scan left and right to find max walls → O(n²).

Step 3 — Optimal insight:

Track maxLeft and maxRight as you walk from both ends. Key rule: if height[L] < height[R], the left side is the bottleneck — you can safely compute water at L using only maxLeft (maxRight is guaranteed >= height[R] >= height[L]).

Step 4 — Algorithm:

1. L=0, R=n-1, maxL=0, maxR=0, water=0

2. If height[L] < height[R]: update maxL or add water at L; L++

3. Else: update maxR or add water at R; R--

Step 5 — Edge cases:

- Flat array: 0 water

- Single bar: 0 water

Way of Thinking: Water at position i = min(maxLeft[i], maxRight[i]) - height[i]. Use two pointers: track maxLeft and maxRight as you go, process the smaller side.

function trap(height) {
  let left = 0, right = height.length - 1;
  let maxLeft = 0, maxRight = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= maxLeft) maxLeft = height[left];
      else water += maxLeft - height[left];
      left++;
    } else {
      if (height[right] >= maxRight) maxRight = height[right];
      else water += maxRight - height[right];
      right--;
    }
  }
  return water;
}

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6

---

Q7. Move Zeros to End [E][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

In-place partition (non-zeros first, zeros at end) = slow/fast same-direction pointers.

Step 2 — Brute force:

Filter non-zeros, count zeros, concatenate → O(n) space.

Step 3 — Optimal insight:

slow tracks next write position for non-zero values. fast scans. Copy non-zeros forward. Then fill tail with zeros.

Step 4 — Algorithm:

1. slow = 0

2. For each fast: if nums[fast] !== 0, nums[slow++] = nums[fast]

3. Fill nums[slow..end] with 0

Step 5 — Edge cases:

- No zeros: no writes to tail

- All zeros: slow stays at 0, fill entire array

Way of Thinking: Slow pointer marks where next non-zero goes. Fast scans. After loop, fill rest with 0s.

function moveZeroes(nums) {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow++] = nums[fast];
    }
  }
  while (slow < nums.length) nums[slow++] = 0;
  return nums;
}

console.log(moveZeroes([0,1,0,3,12])); // [1,3,12,0,0]

---

Q8. Sort Array by Parity [E]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Partition array into two groups in-place → two pointers from both ends.

Step 2 — Brute force:

Filter evens, filter odds, concatenate → O(n) space.

Step 3 — Optimal insight:

Like Dutch National Flag with 2 groups instead of 3. Left pointer finds an odd number, right pointer finds an even number, swap them.

Step 4 — Algorithm:

1. L=0, R=n-1

2. If nums[L] is even: L++

3. If nums[R] is odd: R--

4. Otherwise swap and continue

Step 5 — Edge cases:

- All even or all odd: pointers meet immediately

Way of Thinking: Two pointers from both ends. Swap when even is on right and odd is on left.

function sortArrayByParity(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    if (nums[left] % 2 > nums[right] % 2) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
    }
    if (nums[left] % 2 === 0) left++;
    if (nums[right] % 2 === 1) right--;
  }
  return nums;
}

console.log(sortArrayByParity([3,1,2,4])); // [4,2,3,1] (or any valid)

---

Pattern Summary