algorithms/docs/01-foundations/two-pointers.md

Two Pointers Pattern

Overview

Two pointers is a powerful pattern for solving array and string problems efficiently. It involves using two pointers (indices) that traverse the data structure from different directions or at different speeds.

Core Concepts

Types of Two Pointers

1. Opposite Direction: One pointer starts at beginning, other at end
2. Same Direction: Both pointers start at beginning, move at different speeds
3. Fast/Slow Pointers: Detect cycles in linked lists

Basic Template

function twoPointers(arr: number[]): void {
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) {
        // Process elements at left and right
        const leftVal = arr[left];
        const rightVal = arr[right];
        
        // Move pointers based on condition
        if (condition) {
            left++;
        } else {
            right--;
        }
    }
}

Use Cases

1. Sorted Arrays

Perfect for problems where the array is sorted and you need to find pairs, triplets, or perform operations.

2. Palindrome Checking

Check if a string or array reads the same forwards and backwards.

3. Container Problems

Find maximum area, minimum window, or similar container-based problems.

4. Subarray Problems

Find subarrays that meet certain conditions.

Example Implementations

Two Sum (Sorted Array)

function twoSum(numbers: number[], target: number): number[] {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left <= right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1]; // 1-based indexing
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    
    return [-1, -1];
}

Container With Most Water

function maxArea(height: number[]): number {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;
    
    while (left < right) {
        const currentHeight = Math.min(height[left], height[right]);
        const currentWidth = right - left;
        const currentArea = currentHeight * currentWidth;
        
        maxArea = Math.max(maxArea, currentArea);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Sorted Squares

function sortedSquares(nums: number[]): number[] {
    const result = new Array(nums.length);
    let left = 0;
    let right = nums.length - 1;
    let index = nums.length - 1;
    
    while (left <= right) {
        const leftSquare = nums[left] * nums[left];
        const rightSquare = nums[right] * nums[right];
        
        if (leftSquare > rightSquare) {
            result[index] = leftSquare;
            left++;
        } else {
            result[index] = rightSquare;
            right--;
        }
        index--;
    }
    
    return result;
}

Palindrome Check

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

Time Complexity Analysis

Problem	Time Complexity	Space Complexity	Pattern
Two Sum	O(n)	O(1)	Opposite direction
Max Area	O(n)	O(1)	Opposite direction
Sorted Squares	O(n)	O(n)	Opposite direction
Palindrome	O(n)	O(1)	Opposite direction

Variations

Fast/Slow Pointers (Cycle Detection)

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

Sliding Window (Two Pointers Same Direction)

function maxSlidingWindow(nums: number[], k: number): number[] {
    const result = [];
    const deque = [];
    
    for (let i = 0; i < nums.length; i++) {
        // Remove elements outside window
        while (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }
        
        // Remove elements smaller than current
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        
        deque.push(i);
        
        // Add maximum to result
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
}

Best Practices

1. Pointer Initialization

• Opposite Direction: left = 0, right = arr.length - 1
• Same Direction: left = 0, right = 0 or left = 0, right = 1
• Fast/Slow: slow = head, fast = head

2. Loop Conditions

• Opposite Direction: while (left < right)
• Same Direction: while (right < arr.length)
• Fast/Slow: while (fast && fast.next)

3. Movement Logic

• For sorted arrays: Move pointer based on comparison with target
• For containers: Move pointer pointing to smaller element
• For palindromes: Move both pointers towards center

4. Edge Cases

• Empty array/single element
• All elements same
• Array with negative numbers
• Array with very large values

Common Mistakes

1. Incorrect Loop Condition

// Wrong: includes left === right case
while (left <= right) {
    // This might process the same element twice
}

// Correct: for opposite direction
while (left < right) {
    // Ensures elements are distinct
}

2. Wrong Pointer Movement

// Wrong: always move left
if (sum > target) {
    left++; // Should move right
} else {
    left++;
}

// Correct: move appropriate pointer
if (sum > target) {
    right--;
} else {
    left++;
}

3. Ignoring Edge Cases

// Wrong: no empty array check
while (left < right) {
    // Will fail for empty array

// Correct: add edge case check
if (arr.length === 0) return [];

Practice Problems

Easy

• Two Sum (sorted array)
• Palindrome check
• Valid palindrome II
• Squares of sorted array
• Reverse string

Medium

• Container with most water
• Three sum
• Remove duplicates from sorted array
• Minimum size subarray sum
• Trapping rain water

Hard

• Longest substring without repeating characters
• Substring with concatenation of all words
• Minimum window substring
• Shortest unsorted continuous subarray
• Longest valid parentheses

Real-world Applications

1. Image Processing: Edge detection, feature matching
2. Data Analysis: Time series analysis, moving averages
3. Text Processing: String matching, pattern recognition
4. Signal Processing: Filter design, peak detection

Next Steps

1. Master two pointers pattern with 10+ problems
2. Practice with different array types (sorted, unsorted)
3. Learn sliding window variation
4. Combine with other patterns (hash tables, binary search)

---

Key Takeaway: Two pointers is often the optimal solution for array problems, especially when dealing with sorted data or pairs of elements. Always consider this pattern when you see "sorted array" or "find pairs" in problem statements.