Two Pointers Pattern

1. Opposite Ends Technique (left and right pointers)

Pattern	Initialization	Movement Rule	Use Case
Two Sum Sorted	`left = 0, right = n-1`	Move left if sum too small, right if too large	Find pair with target sum in sorted array
Palindrome Check	`left = 0, right = n-1`	Move both inward while characters match	Verify if string is palindrome
Container Most Water	`left = 0, right = n-1`	Move pointer with smaller height	Maximize area between two vertical lines
Reverse Array	`left = 0, right = n-1`	Swap and move both pointers inward	In-place array reversal

Example: Two sum in sorted array

function twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        
        if (sum === target) {
            return [left, right]; // or [left+1, right+1] for 1-indexed
        } else if (sum < target) {
            left++; // Need larger sum
        } else {
            right--; // Need smaller sum
        }
    }
    
    return [-1, -1]; // Not found
}

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

Example: Valid palindrome

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

// Example
console.log(isPalindrome("A man, a plan, a canal: Panama")); // Output: true

2. Fast and Slow Pointers (Floyd's Cycle Detection)

Pattern	Speed Ratio	Detection	Application
Cycle Detection	Slow: +1, Fast: +2	Fast meets slow inside cycle	Detect loop in linked list (Floyd's algorithm)
Middle Element	Slow: +1, Fast: +2	When fast reaches end, slow at middle	Find middle node of linked list
Cycle Start	Reset one pointer to head after meeting	Both move at same speed, meet at cycle start	Find beginning of cycle in linked list
Happy Number	Fast computes twice per iteration	Converge to 1 or detect cycle	Determine if number is happy number

Example: Detect cycle in linked list

function hasCycle(head) {
    if (!head || !head.next) return false;
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;      // Move 1 step
        fast = fast.next.next; // Move 2 steps
        
        if (slow === fast) {
            return true; // Cycle detected
        }
    }
    
    return false; // No cycle
}

Example: Find middle of linked list

function middleNode(head) {
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // When fast reaches end,
    // slow is at middle
    return slow;
}

// For even length, returns 
// second middle node

Example: Find cycle start position

function detectCycle(head) {
    let slow = head, fast = head;
    
    // Phase 1: Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            // Phase 2: Find cycle start
            slow = head;
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow; // Cycle start
        }
    }
    
    return null; // No cycle
}

3. In-place Array Manipulation O(1) Space

Technique	Pointer Strategy	Space	Common Problem
Remove Duplicates	Slow tracks unique position, fast scans	`O(1)`	Remove duplicates from sorted array
Move Zeros	Slow marks non-zero position, fast scans	`O(1)`	Move all zeros to end of array
Remove Element	Write pointer for valid elements	`O(1)`	Remove all instances of target value
Squares Sorted Array	Compare from both ends, fill from back	`O(n)`	Square sorted array with negatives

Example: Remove duplicates from sorted array

function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    
    let slow = 0; // Position for next unique
    
    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[fast] !== nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    
    return slow + 1; // New length
}

// [1,1,2,2,3] -> [1,2,3,_,_], return 3

Example: Move zeros to end

function moveZeroes(nums) {
    let slow = 0; // Next non-zero position
    
    // Move all non-zeros forward
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    // Fill remaining with zeros
    while (slow < nums.length) {
        nums[slow] = 0;
        slow++;
    }
}

Example: Sorted squares with negative numbers

function sortedSquares(nums) {
    const n = nums.length;
    const result = new Array(n);
    let left = 0, right = n - 1;
    let pos = n - 1; // Fill from back
    
    while (left <= right) {
        const leftSquare = nums[left] * nums[left];
        const rightSquare = nums[right] * nums[right];
        
        if (leftSquare > rightSquare) {
            result[pos] = leftSquare;
            left++;
        } else {
            result[pos] = rightSquare;
            right--;
        }
        pos--;
    }
    
    return result;
}

// [-4,-1,0,3,10] -> [0,1,9,16,100]

4. Partitioning and Sorting Techniques

Algorithm	Invariant	Partitions	Use Case
Dutch National Flag	`[0..low-1]=0, [high+1..n-1]=2`	Three partitions: 0s, 1s, 2s	Sort array with 3 distinct values
QuickSort Partition	Elements < pivot left, > pivot right	Two partitions around pivot	Partition step in quicksort
Partition Array	Reorder by condition	Elements meeting condition first	Separate even/odd, positive/negative
Kth Element	QuickSelect partition	Eliminate half each iteration	Find kth largest/smallest element

Example: Dutch National Flag (Sort colors)

function sortColors(nums) {
    let low = 0;           // Boundary for 0s
    let mid = 0;           // Current element
    let high = nums.length - 1; // Boundary for 2s
    
    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] === 2
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
            // Don't increment mid - need to check swapped element
        }
    }
}

// [2,0,2,1,1,0] -> [0,0,1,1,2,2]

Example: Partition array around pivot

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1; // Index of smaller element
    
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    // Place pivot in correct position
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1; // Pivot index
}

5. Collision Detection Patterns

Pattern	Scenario	Detection Method	Application
Meeting Point	Pointers converge from opposite ends	Check if pointers cross or meet	Binary search, palindrome validation
Circular Collision	Fast pointer catches slow in cycle	Fast laps slow pointer	Linked list cycle detection
Gap Closure	Distance between pointers decreases	Monitor pointer distance	Container with most water
Boundary Check	Pointers reach array bounds	Index validation before access	Prevent out-of-bounds errors

Example: Remove nth node from end of list

function removeNthFromEnd(head, n) {
    const dummy = { next: head };
    let fast = dummy;
    let slow = dummy;
    
    // Move fast n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // Move both until fast reaches end
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // Remove nth node
    slow.next = slow.next.next;
    
    return dummy.next;
}

6. Space Optimization O(1) Complexity

Technique	Space Saved	Trade-off	Example
In-place Modification	`O(n) → O(1)`	May modify input array	Remove duplicates, move zeros
Pointer Instead of Copy	Avoid array cloning	Need to track positions carefully	Reverse string, partition array
Overwrite Strategy	Reuse input array for output	Original data lost	Merge sorted arrays in-place
Cycle Detection Memory	`O(n) → O(1)`	Only works for cyclic structures	Floyd's algorithm vs HashSet

Example: Reverse string in-place

function reverseString(s) {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        // Swap characters
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
    
    // O(1) space - no extra array needed
}

// ['h','e','l','l','o'] -> ['o','l','l','e','h']

Note: Two pointers technique achieves O(1) space complexity for many problems that would otherwise require O(n) space. The key is recognizing when pointers can replace additional data structures like HashSets or extra arrays.

Two Pointers Pattern Summary

Opposite Ends: Start from both ends, move based on condition (sorted arrays)
Fast-Slow: Different speeds reveal patterns (cycle detection, middle element)
Same Direction: One tracks position, other scans (remove duplicates)
Partitioning: Maintain invariants between pointer regions (Dutch flag)
Key Benefit: O(n) time with O(1) space - optimal for in-place operations

Warning: Always validate pointer positions before dereferencing. In fast-slow patterns, check both fast and fast.next to prevent null pointer errors. For opposite-ends technique, ensure left < right condition is correct.

Related Cheat Sheets

Algorithm Patterns