Two Pointer

A comprehensive guide to mastering two-pointer patterns for Data Structures and Algorithms interviews and competitive programming.

Table of Contents

1. Introduction
2. Core Patterns
3. Linked List Applications
4. Array Applications
5. String Applications
6. Advanced Techniques
7. Problem-Solving Framework
8. Practice Problems

---

Introduction

The Two Pointer Technique is a powerful algorithmic pattern that uses two pointers to traverse data structures efficiently. It's particularly effective for:

• Reducing time complexity from O(n²) to O(n)
• Solving problems involving pairs, subarrays, or subsequences
• Optimizing space usage by avoiding extra data structures

When to Use Two Pointers

✅ Use when you see:

• Sorted arrays or linked lists
• Finding pairs with specific properties
• Palindrome checks
• Cycle detection
• Finding middle elements
• Sliding window problems

❌ Avoid when:

• Data is completely unsorted and can't be sorted
• Need to maintain original order strictly
• Problem requires complex backtracking

---

Core Patterns

1. Opposite Direction (Converging Pointers)

Pointers start at opposite ends and move toward each other.

function twoPointerConverging(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const sum = arr[left] + arr[right];

        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return [-1, -1]; // Not found
}

Time Complexity: O(n) | Space Complexity: O(1)

2. Same Direction (Fast/Slow Pointers)

Both pointers move in the same direction at different speeds.

function twoPointerSameDirection(arr) {
    let slow = 0;
    let fast = 0;

    while (fast < arr.length) {
        // Process element at fast pointer
        if (shouldIncludeSlow(arr[fast])) {
            arr[slow] = arr[fast];
            slow++;
        }
        fast++;
    }

    return slow; // New length or position
}

3. Gap Method (Fixed Distance)

One pointer maintains a fixed distance from the other.

function gapMethod(arr, k) {
    let first = 0;
    let second = 0;

    // Create gap of k positions
    for (let i = 0; i < k && first < arr.length; i++) {
        first++;
    }

    // Move both pointers
    while (first < arr.length) {
        // Process pair at (second, first)
        first++;
        second++;
    }

    return second;
}

---

Linked List Applications

1. Find Middle Node (Floyd's Tortoise and Hare)

Problem: Find the middle node of a linked list in one pass.

function findMiddle(head) {
    if (!head) return null;

    let slow = head;  // Tortoise
    let fast = head;  // Hare

    while (fast && fast.next) {
        slow = slow.next;        // Move 1 step
        fast = fast.next.next;   // Move 2 steps
    }

    return slow; // Middle node
}

Why it works: When fast pointer reaches the end, slow pointer is at the middle.

💡 Pro Tip: For even-length lists, this returns the second middle node. To get the first middle node, modify the condition to fast.next && fast.next.next.

2. Detect Cycle (Floyd's Cycle Detection)

Problem: Determine if a linked list has a cycle.

function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

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

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

    return false; // No cycle
}

Algorithm Insight: If there's a cycle, the fast pointer will eventually "lap" the slow pointer.

3. Find Cycle Start Node

Problem: If a cycle exists, find where it begins.

function detectCycleStart(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Phase 1: Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            break; // Cycle found
        }
    }

    // No cycle
    if (!fast || !fast.next) return null;

    // Phase 2: Find cycle start
    slow = head; // Reset slow to head
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next; // Move both at same speed
    }

    return slow; // Cycle start node
}

Mathematical Proof: Distance from head to cycle start equals distance from meeting point to cycle start.

4. Remove Nth Node from End

Problem: Remove the nth node from the end of a linked list.

function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;

    let first = dummy;
    let second = dummy;

    // Create gap of n+1 positions
    for (let i = 0; i <= n; i++) {
        first = first.next;
    }

    // Move both pointers until first reaches end
    while (first) {
        first = first.next;
        second = second.next;
    }

    // Remove the nth node
    second.next = second.next.next;

    return dummy.next;
}

Technique: Using dummy node handles edge case of removing the head.

5. Find Intersection of Two Lists

Problem: Find the node where two linked lists intersect.

function getIntersectionNode(headA, headB) {
    if (!headA || !headB) return null;

    let pA = headA;
    let pB = headB;

    // Each pointer traverses both lists
    while (pA !== pB) {
        pA = pA ? pA.next : headB; // Switch to other list when done
        pB = pB ? pB.next : headA;
    }

    return pA; // Intersection node or null
}

Elegant Solution: Each pointer travels the same total distance, meeting at intersection or null.

---

Array Applications

1. Two Sum (Sorted Array)

Problem: Find two numbers that add up to a target in a 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];
        } else if (sum < target) {
            left++; // Need larger sum
        } else {
            right--; // Need smaller sum
        }
    }

    return []; // No solution
}

2. Three Sum

Problem: Find all unique triplets that sum to zero.

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

    for (let i = 0; i < nums.length - 2; i++) {
        // Skip duplicates for first number
        if (i > 0 && nums[i] === nums[i - 1]) continue;

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

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

            if (sum === target) {
                result.push([nums[i], nums[left], nums[right]]);

                // Skip duplicates
                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;
}

3. Container With Most Water

Problem: Find two lines that together form a container holding the most water.

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

    while (left < right) {
        const width = right - left;
        const currentHeight = Math.min(height[left], height[right]);
        const water = width * currentHeight;

        maxWater = Math.max(maxWater, water);

        // Move pointer with smaller height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

Key Insight: Always move the pointer with the smaller height to potentially find a larger area.

4. Remove Duplicates from Sorted Array

Problem: Remove duplicates in-place from a sorted array.

function removeDuplicates(nums) {
    if (nums.length <= 1) return nums.length;

    let slow = 0; // Points to last unique element

    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[fast] !== nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }

    return slow + 1; // New length
}

5. Move Zeros

Problem: Move all zeros to the end while maintaining relative order.

function moveZeroes(nums) {
    let slow = 0; // Points to next position for non-zero

    // Move all non-zero elements to front
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    // Fill remaining positions with zeros
    while (slow < nums.length) {
        nums[slow] = 0;
        slow++;
    }
}

---

String Applications

1. Valid Palindrome

Problem: Check if a string is a palindrome, ignoring non-alphanumeric characters.

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

    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !isAlphaNumeric(s[left])) {
            left++;
        }
        while (left < right && !isAlphaNumeric(s[right])) {
            right--;
        }

        // Compare characters (case-insensitive)
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

function isAlphaNumeric(char) {
    return /[a-zA-Z0-9]/.test(char);
}

2. Reverse Words in String

Problem: Reverse the order of words in a string.

function reverseWords(s) {
    // Convert to array and clean up spaces
    const chars = s.trim().split('');

    // Reverse entire string
    reverse(chars, 0, chars.length - 1);

    // Reverse each word back
    let start = 0;
    for (let i = 0; i <= chars.length; i++) {
        if (i === chars.length || chars[i] === ' ') {
            reverse(chars, start, i - 1);
            start = i + 1;
        }
    }

    return chars.join('').replace(/\s+/g, ' ');
}

function reverse(arr, left, right) {
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

3. Longest Palindromic Substring

Problem: Find the longest palindromic substring.

function longestPalindrome(s) {
    if (!s || s.length < 2) return s;

    let start = 0;
    let maxLength = 1;

    for (let i = 0; i < s.length; i++) {
        // Check for odd-length palindromes
        const len1 = expandAroundCenter(s, i, i);

        // Check for even-length palindromes
        const len2 = expandAroundCenter(s, i, i + 1);

        const currentMax = Math.max(len1, len2);

        if (currentMax > maxLength) {
            maxLength = currentMax;
            start = i - Math.floor((currentMax - 1) / 2);
        }
    }

    return s.substring(start, start + maxLength);
}

function expandAroundCenter(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

---

Advanced Techniques

1. Sliding Window with Two Pointers

Problem: Find the minimum window substring containing all characters of pattern.

function minWindow(s, t) {
    if (s.length < t.length) return "";

    // Character frequency map for pattern
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }

    let left = 0;
    let right = 0;
    let formed = 0; // Characters satisfied
    let minLen = Infinity;
    let minStart = 0;

    const windowCounts = new Map();

    while (right < s.length) {
        // Expand window
        const char = s[right];
        windowCounts.set(char, (windowCounts.get(char) || 0) + 1);

        if (need.has(char) && windowCounts.get(char) === need.get(char)) {
            formed++;
        }

        // Contract window
        while (formed === need.size && left <= right) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            const leftChar = s[left];
            windowCounts.set(leftChar, windowCounts.get(leftChar) - 1);

            if (need.has(leftChar) && windowCounts.get(leftChar) < need.get(leftChar)) {
                formed--;
            }

            left++;
        }

        right++;
    }

    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

2. Dutch National Flag (Three Pointers)

Problem: Sort array of 0s, 1s, and 2s in-place.

function sortColors(nums) {
    let left = 0;   // Next position for 0
    let right = nums.length - 1;  // Next position for 2
    let current = 0; // Current element

    while (current <= right) {
        if (nums[current] === 0) {
            [nums[left], nums[current]] = [nums[current], nums[left]];
            left++;
            current++;
        } else if (nums[current] === 2) {
            [nums[current], nums[right]] = [nums[right], nums[current]];
            right--;
            // Don't increment current (need to check swapped element)
        } else {
            current++; // nums[current] === 1
        }
    }
}

3. Trapping Rain Water

Problem: Calculate how much water can be trapped after raining.

function trap(height) {
    if (height.length < 3) return 0;

    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let water = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }

    return water;
}

---

Problem-Solving Framework

Step-by-Step Approach

1. Identify the Pattern

   • Is the data sorted?
   • Are we looking for pairs/triplets?
   • Do we need to find cycles or middle elements?

2. Choose Pointer Strategy

   • Converging: Opposite ends moving toward each other
   • Same Direction: Fast/slow or gap method
   • Expanding: From center outward

3. Handle Edge Cases

   • Empty inputs
   • Single element
   • All elements are the same

4. Optimize

   • Can we avoid extra space?
   • Can we reduce the number of comparisons?

Template Code

function twoPointerTemplate(input) {
    // Initialize pointers based on pattern
    let left = 0;
    let right = input.length - 1; // or other initialization

    while (/* termination condition */) {
        // Process current state
        if (/* condition met */) {
            // Found solution or update result
            return result;
        } else if (/* need to move left */) {
            left++;
        } else if (/* need to move right */) {
            right--;
        }

        // Handle duplicates if necessary
        // Update other variables
    }

    return /* default result */;
}

---

Practice Problems

Beginner Level

1. Two Sum II (Sorted array)
2. Remove Duplicates from Sorted Array
3. Valid Palindrome
4. Move Zeroes
5. Reverse String

Intermediate Level

1. 3Sum
2. Container With Most Water
3. Find the Duplicate Number
4. Linked List Cycle II
5. Sort Colors

Advanced Level

1. Minimum Window Substring
2. Trapping Rain Water
3. 4Sum
4. Palindromic Substrings
5. Shortest Unsorted Continuous Subarray

---

Time Complexity Analysis

Pattern	Typical Time	Typical Space	Use Cases
Converging Pointers	O(n)	O(1)	Two Sum, Palindrome
Fast/Slow Pointers	O(n)	O(1)	Cycle Detection, Middle
Gap Method	O(n)	O(1)	Nth from End
Sliding Window	O(n)	O(k)	Substring Problems
Expanding Centers	O(n²)	O(1)	Palindrome Expansion

---

Key Takeaways

✅ Advantages

• Time Efficient: Often reduces O(n²) to O(n)
• Space Efficient: Usually O(1) extra space
• Simple Logic: Easy to understand and implement
• Versatile: Works on arrays, strings, and linked lists

⚠️ Common Pitfalls

• Off-by-one errors in pointer initialization
• Infinite loops from incorrect pointer updates
• Missing edge cases like empty inputs
• Not handling duplicates properly

🎯 Best Practices

• Draw diagrams to visualize pointer movement
• Test with small examples first
• Handle edge cases explicitly
• Use meaningful variable names
• Comment your pointer logic

---

Cheat Sheet

// Converging Pointers (Two Sum)
let left = 0, right = arr.length - 1;
while (left < right) {
    if (condition) return result;
    else if (needSmaller) right--;
    else left++;
}

// Fast/Slow (Cycle Detection)
let slow = head, fast = head;
while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
}

// Gap Method (Nth from End)
let first = head, second = head;
for (let i = 0; i < n; i++) first = first.next;
while (first) {
    first = first.next;
    second = second.next;
}

// Same Direction (Remove Duplicates)
let slow = 0;
for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
        arr[++slow] = arr[fast];
    }
}

---