Two Pointers Pattern: Opposing, Fast-Slow & In-Place Moves

Pairwise array searches naturally yield O(N^2) quadratic complexity if implemented with nested loops. The Two Pointers Pattern reduces this runtime to a clean linear O(N) by utilizing the geometric or sorted structure of data to eliminate vast swaths of invalid combinations in a single pointer step.

Rather than checking every pair (i, j), two pointers navigate the sequence based on a deterministic invariant: moving one pointer either strictly increases, strictly decreases, or filters candidate solutions.

The Three Primary Two-Pointer Variants

flowchart TD
    subgraph Variants["Two Pointer Traversal Archetypes"]
        Opposite["1. Converging (Opposite Ends)\nleft = 0, right = N - 1\nUsed for: Sorted Two Sum, Container with Water, Palindromes"]
        SameDir["2. Reader-Writer (Same Direction)\nwriter = 0, reader = 0\nUsed for: In-place deduplication, Move Zeroes, Partitioning"]
        TwoSeq["3. Two Independent Sequences\np1 = 0 (Arr1), p2 = 0 (Arr2)\nUsed for: Merging sorted lists, Array intersections"]
    end

Pattern 1: Converging Pointers (Two Sum in Sorted Array)

In a sorted array, nums[left] + nums[right] gives a monotonic spectrum:

• If sum < target: The only way to increase the sum is to increment left (move toward larger values).
• If sum > target: The only way to decrease the sum is to decrement right (move toward smaller values).
• If sum == target: Solution located.

flowchart TD
    A["left = 0, right = len - 1"] --> B{"left < right ?"}
    B -->|No| NotFound(["No Pair Found"])
    B -->|Yes| Calc["sum = nums[left] + nums[right]"]
    Calc --> Comp{"Compare sum to target"}
    Comp -->|sum == target| Found(["Return [left, right]"])
    Comp -->|sum < target| Inc["Sum too small:\nleft++"]
    Comp -->|sum > target| Dec["Sum too large:\nright--"]
    Inc --> B
    Dec --> B

Java Implementation (3Sum with Duplicate Pruning)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSumSolver {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) return result;

        Arrays.sort(nums); // O(N log N)

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicate anchors
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i];

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Skip duplicate left and right values
                    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;
    }
}

Pattern 2: Container With Most Water (Greedy Convergence)

Given vertical lines of varying heights, find two lines that form a container storing maximum water: area = (right - left) × min(height[left], height[right]).

The Proof of Pointer Movement: The width (right - left) is maximal at the start and decreases with every step. To find a larger area, the bottleneck—the shorter line—must be replaced. Moving the taller line can only produce smaller or equal heights across a narrower width, guaranteeing no optimal solution is lost when moving the shorter pointer inward.

Python Implementation

def max_area(height: list[int]) -> int:
    """Calculates max water container capacity in O(N) time and O(1) space."""
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h_left, h_right = height[left], height[right]
        current_water = width * min(h_left, h_right)
        max_water = max(max_water, current_water)

        # Always eliminate the bottleneck (the shorter bar)
        if h_left < h_right:
            left += 1
        else:
            right -= 1

    return max_water

Pattern 3: In-Place Modification (Reader vs. Writer Pointers)

When asked to remove duplicates or filter values in-place without allocating a second array, use a writer pointer that tracks the next clean insertion index and a reader pointer that scans forward.

TypeScript Implementation

export function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let writer = 1;

  for (let reader = 1; reader < nums.length; reader++) {
    // When reader finds a new distinct value, copy it to writer's position
    if (nums[reader] !== nums[reader - 1]) {
      nums[writer] = nums[reader];
      writer++;
    }
  }

  // writer equals length of unique elements
  return writer;
}

Critical Pitfalls & Invariants

• Sorting Requirement: Converging pointer arithmetic (sum < target ⇒ left++) is only valid on sorted arrays. If sorting is not allowed or elements must maintain original indexes, use a Hash Map (O(N) space) instead.
• Duplicate Skipped Elements: In triplet or quadruplet searches (e.g., 3Sum / 4Sum), always skip identical adjacent elements after recording a valid match to avoid duplicate solution sets.
• Strict Invariant Tracking: Determine before writing code whether pointers should meet (left <= right for binary search / odd-palindrome checks) or stop before collision (left < right for distinct pairs).

Complexity Summary