Chapter 5a — Two Pointer Problem Patterns

Two pointers solves one class of problems: when the data has structure that lets a single move of one pointer eliminate an entire region of search space.

Pattern Map

Problem 1: Valid Palindrome II

Problem: Given a string, return true if it can be a palindrome after deleting at most one character.
validPalindrome("abca") → true (delete 'b' or 'c')
LeetCode 680. Meta/Facebook. Asked at Zepto.

Four Questions

Q1: What do I have? A string. May not be a palindrome. One deletion allowed.
Q2: What do I want? Can we delete at most 1 character and get a palindrome?
Q3: What is the brute force? Try deleting each character, check if result is palindrome. O(n²).
Q4: Where is the waste? Two pointers converge from both ends. When characters match, no deletion needed. When they don't match, exactly one of the two characters must be deleted — try both.

Implementation

function validPalindrome(s) {
  let left = 0, right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      // One mismatch: try deleting left character OR right character
      // If either resulting substring is a palindrome, return true
      return isPalin(s, left + 1, right) || isPalin(s, left, right - 1);
    }
    left++;
    right--;
  }

  return true;  // no mismatches → already a palindrome
}

function isPalin(s, left, right) {
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

Dry Run: validPalindrome("abca")

left=0('a'), right=3('a'). Match. left=1, right=2.
left=1('b'), right=2('c'). Mismatch!
  Try delete left (skip 'b'): isPalin("abca", 2, 2) = isPalin on "c"
    left=2, right=2. left >= right → return true. ✓
  return true. ✓

Dry Run: validPalindrome("eeccccbebaeeabebccceea")

This is a harder case. Pointers converge, hit a mismatch at some point. The key: we only recurse once after the first mismatch. Those recursive calls do no further branching — it's a clean palindrome check. So total work is still O(n).

Complexity: O(n) time (at most two passes of length n), O(1) space.

Why not more than one mismatch? The problem says at most one deletion. Once we find the first mismatch and try the two options, we've "used" our deletion. The recursive isPalin check has no more deletions allowed — if either option fails, we can't delete again.

Problem 2: Squares of a Sorted Array

Problem: Given a sorted integer array (with negatives), return the sorted squares.
sortedSquares([-4,-1,0,3,10]) → [0,1,9,16,100]
LeetCode 977.

Four Questions

Q1: What do I have? Sorted array with possible negatives. Squares of negatives are positive and potentially large.
Q2: What do I want? Array of squares, sorted in ascending order.
Q3: What is the brute force? Square all, then sort. O(n log n).
Q4: Where is the waste? The largest squares are at the two ends (most negative or most positive). Opposite-ends two pointers: compare nums[left]² and nums[right]², place the larger one at the end of result array, move that pointer inward. Fills result from back to front.

Implementation

function sortedSquares(nums) {
  const result = new Array(nums.length);
  let left = 0, right = nums.length - 1;
  let pos = nums.length - 1;  // fill result from back

  while (left <= right) {
    const leftSq = nums[left] * nums[left];
    const rightSq = nums[right] * nums[right];

    if (leftSq > rightSq) {
      result[pos] = leftSq;
      left++;
    } else {
      result[pos] = rightSq;
      right--;
    }
    pos--;
  }

  return result;
}

Dry Run: sortedSquares([-4,-1,0,3,10])

State: nums=[-4,-1,0,3,10], left=0, right=4, pos=4
result=[ , , , , ]

pos=4: leftSq=(-4)²=16, rightSq=10²=100. 100>16 → result[4]=100, right=3.
pos=3: leftSq=16, rightSq=3²=9. 16>9 → result[3]=16, left=1.
pos=2: leftSq=(-1)²=1, rightSq=9. 9>1 → result[2]=9, right=2.
pos=1: leftSq=1, rightSq=0²=0. 1>0 → result[1]=1, left=2.
pos=0: left=2=right=2. leftSq=0, rightSq=0. rightSq>=leftSq → result[0]=0, right=1.
left=2 > right=1. Loop ends.

result=[0,1,9,16,100] ✓

Complexity: O(n) time, O(n) space (output array — unavoidable since we must return sorted squares).

Key insight: Filling from back is the trick. We don't know the smallest square yet (it's somewhere in the middle), but we always know the largest (whichever end is larger in absolute value). Work with what you know.

Problem 3: Three Sum

Problem: Find all unique triplets that sum to zero.
threeSum([-1,0,1,2,-1,-4]) → [[-1,-1,2],[-1,0,1]]
LeetCode 15. #3 most asked array problem globally. Razorpay, Amazon, Microsoft.

This was fully developed in Chapter 5. Here is the implementation with annotated deduplication:

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    // Dedup outer: if same as previous i, skip
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    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]]);
        // Dedup inner: skip duplicates at left and 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;
}

Extended Dry Run: threeSum([-2,0,0,2,2])

Sort: [-2,0,0,2,2] (already sorted)

i=0, nums[0]=-2. left=1, right=4.

sum=-2+0+2=0 ✓ push [-2,0,2].
  nums[left+1]=nums[2]=0 === nums[1]=0 → left=2 (skip dup).
  nums[right-1]=nums[3]=2 === nums[4]=2 → right=3 (skip dup).
  left=3, right=2. left > right → inner loop ends.

i=1, nums[1]=0. left=2, right=4.

sum=0+0+2=2 > 0 → right=3.
sum=0+0+2=2 > 0 → right=2.
left=2 >= right=2 → inner loop ends.

i=2, nums[2]=0. i>0 and nums[2]==nums[1] → skip (dup).

i=3, nums[3]=2. length-2=3, so i<length-2 fails (3<3 is false). Loop ends.

Result: [[-2,0,2]] ✓

Why the inner dedup while loop must check left < right: If we blindly advance past duplicates, we could overshoot and have left >= right, making the next comparison invalid. The guard prevents this.

Problem 4: Four Sum

Problem: Find all unique quadruplets summing to target.
fourSum([1,0,-1,0,-2,2], 0) → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
LeetCode 18.

Four Questions

Q1: What do I have? Unsorted array, integer target.
Q2: What do I want? All unique quadruplets summing to target.
Q3: What is the brute force? Four nested loops. O(n⁴).
Q4: Where is the waste? Three Sum reduced to Two Sum by fixing one variable. Four Sum reduces to Two Sum by fixing two variables. Sort + two outer loops + two-pointer inner.

function fourSum(nums, target) {
  nums.sort((a, b) => a - b);
  const result = [];
  const n = nums.length;

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;  // dedup i

    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;  // dedup j

      let left = j + 1, right = n - 1;

      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];

        if (sum === target) {
          result.push([nums[i], nums[j], 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 < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }

  return result;
}

Complexity: O(n³) time — two outer loops O(n²), inner two-pointer O(n). Space O(1).

The k-Sum pattern: This generalizes. k-Sum reduces to 2-Sum by fixing k-2 variables in nested loops. Time complexity: O(n^(k-1)). 2Sum with HashMap: O(n). 3Sum: O(n²). 4Sum: O(n³).

Problem 5: Remove Nth Node From End of List

Problem: Given a linked list, remove the nth node from the end and return the head.
removeNthFromEnd([1,2,3,4,5], n=2) → [1,2,3,5]
LeetCode 19. One-pass. Microsoft, Amazon.

Four Questions

Q1: What do I have? A singly linked list. n is guaranteed valid.
Q2: What do I want? Remove the nth-from-last node in one pass.
Q3: What is the brute force? Traverse to find length L, then traverse again to position L-n. Two passes.
Q4: Where is the waste? Two passes over the same list. Fast/slow pointers can solve this in one pass: advance fast pointer n steps ahead, then move both until fast reaches end. Slow will be at the node just before the target.

Implementation

function removeNthFromEnd(head, n) {
  // Dummy node before head handles edge case of removing head itself
  const dummy = { val: 0, next: head };
  let fast = dummy;
  let slow = dummy;

  // Advance fast n+1 steps (so slow stops one before the target)
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  // Move both until fast reaches null
  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  // slow.next is the node to remove
  slow.next = slow.next.next;

  return dummy.next;
}

Dry Run: removeNthFromEnd([1,2,3,4,5], n=2)

List: dummy → 1 → 2 → 3 → 4 → 5 → null
fast = dummy, slow = dummy.

Advance fast n+1=3 steps:
  i=0: fast = 1
  i=1: fast = 2
  i=2: fast = 3

State: fast=node(3), slow=dummy.

Move both until fast===null:
  fast=4, slow=1.
  fast=5, slow=2.
  fast=null, slow=3.

slow.next = node(4). slow.next.next = node(5).
slow.next = node(5). (skip node(4))

Result: dummy → 1 → 2 → 3 → 5 → null
return dummy.next = node(1). ✓

Why n+1 steps for fast? We want slow to stop at the node before the one to delete (so we can change slow.next). If fast goes n steps ahead, then when fast reaches the last node, slow is at position (L-n) — the target itself. We need slow at (L-n-1), one before. So fast must be n+1 steps ahead, landing at null when slow is at (L-n-1).

Why dummy node? If the list is [1] and n=1, we're removing the head. slow.next = slow.next.next would require slow to be before the head. The dummy node provides that position.

Complexity: O(L) time where L is list length. O(1) space.

Problem 6: Sort Colors (Dutch National Flag)

Problem: Sort an array of 0s, 1s, 2s in-place.
sortColors([2,0,2,1,1,0]) → [0,0,1,1,2,2]
LeetCode 75. Three-pointer variant of the fast/slow pattern.

This was covered in Chapter 5. Restating here as a pattern example.

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // Don't advance mid — newly swapped element at mid is unknown
    }
  }
}

The three-pointer insight: Three partitions require three boundaries. low tracks where 0s end. mid is the unknown frontier. high tracks where 2s begin. The region [mid, high] is unknown at any point.

Dry run: sortColors([1,2,0])

low=0, mid=0, high=2. nums=[1,2,0].

mid=0: nums[0]=1 → mid=1.
mid=1: nums[1]=2 → swap nums[1] and nums[2]: [1,0,2]. high=1.
mid=1: nums[1]=0 → swap nums[0] and nums[1]: [0,1,2]. low=1, mid=2.
mid=2 > high=1. Loop ends.

Result: [0,1,2] ✓

Problem 7: Minimum Absolute Difference (Sorted Pair)

Problem: Given a sorted array, find all pairs with the minimum absolute difference.
minimumAbsDifference([-4,-2,0,3]) → [[-4,-2],[-2,0]] (both have difference 2)
LeetCode 1200.

Four Questions

Q1: What do I have? A sorted array.
Q2: What do I want? All pairs [a, b] where b - a is minimized (and a < b).
Q3: What is the brute force? Check all pairs. O(n²).
Q4: Where is the waste? In a sorted array, the minimum difference must be between adjacent elements (non-adjacent elements are farther apart). So we only need to scan adjacent pairs.

This is the simplest possible two-pointer: adjacent elements, i and i+1. Not truly two separate pointers but the same mental model — adjacent window moving forward.

function minimumAbsDifference(arr) {
  // arr is already sorted per problem statement
  let minDiff = Infinity;

  // Find minimum difference
  for (let i = 0; i < arr.length - 1; i++) {
    minDiff = Math.min(minDiff, arr[i + 1] - arr[i]);
  }

  // Collect all pairs with that difference
  const result = [];
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i + 1] - arr[i] === minDiff) {
      result.push([arr[i], arr[i + 1]]);
    }
  }

  return result;
}

Dry run: minimumAbsDifference([4,2,1,3])

Wait — sort first: [1,2,3,4]. Differences: 1,1,1. minDiff=1. All adjacent pairs: [[1,2],[2,3],[3,4]].

Complexity: O(n) time (two linear scans). O(1) space.

Why this matters: This problem teaches that "find minimum difference" in a sorted array collapses from O(n²) to O(n) via the structural insight that adjacency = minimum distance. The same reasoning appears in many sorted-array problems.

Problem 8: Linked List Cycle Detection (Floyd's Algorithm)

Problem: Given a linked list, determine if it has a cycle.
LeetCode 141. Classic. Every company.

Four Questions

Q1: What do I have? A linked list. Nodes may form a cycle (last node points back to a prior node).
Q2: What do I want? Return true if cycle exists.
Q3: What is the brute force? Use a HashSet — store visited nodes, return true when you see one twice. O(n) time, O(n) space.
Q4: Where is the waste? The HashSet uses O(n) space. Can we detect a cycle with O(1) space?

Floyd's Cycle Detection (Tortoise and Hare)

Insight: If there's a cycle, a fast pointer (2 steps at a time) will lap a slow pointer (1 step at a time) — they must eventually meet. If there's no cycle, the fast pointer reaches null.

Why they must meet (if cycle exists):

• Once both pointers are inside the cycle, the fast pointer gains 1 step on the slow pointer each iteration.
• Eventually the gap between them closes to 0 — they meet.
• The cycle has finite length k. The gap starts at some value g < k and decreases by 1 each step. After g steps, gap = 0. They meet.

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) return true;  // cycle detected
  }

  return false;  // fast reached null — no cycle
}

Dry Run: hasCycle([3,2,0,-4], pos=1) (tail connects to index 1)

List: 3 → 2 → 0 → -4 → (back to 2)

slow=3, fast=3.

Iteration 1: slow=2, fast=0.
Iteration 2: slow=0, fast=2.   (fast: -4 → 2)
Iteration 3: slow=-4, fast=-4. (slow: 0→-4, fast: 0→-4)

slow === fast → return true. ✓

Dry Run: hasCycle([1,2]) (no cycle)

slow=1, fast=1.

Iteration 1: slow=2, fast=null. (fast.next.next: 2.next=null, null.next — wait)

Careful: fast.next !== null check prevents fast.next.next from crashing. At fast=2, fast.next=null, so condition fast.next !== null fails → loop exits. return false. ✓

Complexity: O(n) time, O(1) space.

Extended problem (LeetCode 142 — Find where cycle starts): When slow and fast meet, reset slow to head. Advance both one step at a time. They meet at the cycle start. The math: if the pre-cycle length is F and cycle length is C, they first meet at F steps into the cycle. Resetting slow to head and advancing both at the same speed converges them at the cycle entry after F more steps. The proof uses modular arithmetic on distances — a beautiful result.

Pattern Recognition Decision Tree

New two-pointer problem:

1. Is the array/string sorted (or can we sort it)?
   YES:
     a. Finding pairs/triplets with a sum target?
        → Opposite ends. Fix outer variables, two-pointer inner.
     b. Checking symmetry?
        → Opposite ends. Converge inward, compare.
     c. Squares / transformed values need merging?
        → Opposite ends. Fill result from back (largest first).
   NO:
     a. In-place partition / remove / deduplicate?
        → Fast/slow. slow=write head, fast=read head.
     b. Linked list problem: cycle? nth from end?
        → Fast/slow. fast moves ahead or faster.

2. Is there a monotonic property?
   (As left increases, sum/area/product only changes in one direction)
   → Move the pointer that can improve the condition.

3. One deletion allowed?
   → Run opposite ends; on first mismatch, try two subproblems recursively.

5 Practice Problems

1. Trace and Predict

function f(s, t) {
  let i = 0, j = 0;
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) j++;
    i++;
  }
  return j === t.length;
}

What does f compute? Trace f("ahbgdc", "abc") and f("ahbgdc", "axc"). What is the time complexity? What is the space complexity? Name this problem (it appears on LeetCode).

2. Find the Waste

Naive approach for "find if any two numbers in an unsorted array sum to target":

for i: for j>i: if nums[i]+nums[j]===target return true

O(n²). You know two approaches: HashMap (O(n) time, O(n) space) and Two Pointers on sorted array (O(n log n) time, O(1) space). Given these tradeoffs, when would you choose each? Design a scenario where the HashMap approach is strictly better and one where two pointers is strictly better.

3. Failure Analysis

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

This is a variant that starts fast = head.next. Does it work correctly? Trace it on [1] (single node, no cycle). What happens? Is there a bug? If yes, fix it.

4. Design Under Constraints

Design a function longestPalindromeSubstring(s) that finds the longest palindromic substring. You cannot use dynamic programming (that's Chapter 13). Use the "expand around center" technique — for each character (and each gap between characters), expand outward using two pointers as long as characters match.

Write the code. What is the time complexity? What is the space complexity? (Hint: there are 2n-1 centers for a string of length n — n characters and n-1 gaps.)

5. Reach Beyond

Given a sorted array nums and an integer k, find the number of pairs with absolute difference exactly equal to k.
Example: nums=[1,2,3,4,5], k=2 → 3 (pairs: (1,3), (2,4), (3,5)).

Design an O(n) two-pointer solution. Hint: fix the left pointer, advance right until nums[right] - nums[left] >= k. Check if it equals k. Advance left. Handle counting carefully — don't double-count.

Then: what if duplicates exist? nums=[1,1,2,3,3], k=2 → how do you handle pairs (1,3) where there are multiple 1s and 3s? Count them as separate pairs or unique pairs only?

Connect Forward

Chapter 6 — Sliding Window is the natural extension. The "window" between two same-direction pointers is the key structure. Instead of a fixed condition (find a pair), you maintain a property across a variable-size window (find the longest substring with at most k distinct characters).

The critical shift: in two pointers (Pattern B), we move pointers to find a single position. In sliding window, we expand and contract the window to find an optimal range. Both use two indices. The difference is what we're optimizing.