Coding Interview Patterns: Two Pointers

Table of Contents

Introduction

The two pointers technique is one of the most elegant and efficient patterns in algorithmic problem-solving. This approach uses two references (pointers) to traverse data structures strategically, often reducing time complexity from O(n²) to O(n).

Whether you’re preparing for coding interviews at top tech companies or optimizing production code, mastering this pattern will significantly enhance your problem-solving toolkit.

As the name implies, this technique involves using two pointers that traverse a data structure in a coordinated way, starting from different positions or moving in opposite directions. These pointers adjust dynamically based on specific conditions, enabling efficient data exploration with optimal time and space complexity.

When to use it?

To determine if your problem is a match for the two pointer pattern, consider the following criteria:

1. Comparing Elements: If the problem involves comparing elements in a data structure (like an array or a string) to find pairs that satisfy a certain condition, the two pointer technique might be suitable.

2. Single or Opposite Directions: If the problem can benefit from traversing the data structure in one or both directions simultaneously, it’s a good indicator that the two pointer pattern is applicable.

3. Optimal Efficiency: If the problem requires an efficient solution in terms of time and space complexity, the two pointer technique often provides a way to achieve this, especially when compared to brute force methods.

4. Sorted Data: Many problems that use the two pointer technique involve sorted data, although this is not a strict requirement. Sorting can often simplify the implementation and improve efficiency.

Two Pointers in Action

The two pointers technique becomes clearer when we see it in action. The interactive demo below shows how this pattern works with a palindrome checker:

Use the “Next” and “Prev” buttons to step through the algorithm and observe how the pointers move toward each other, comparing characters at each step.

Example: isPalindrome

Consider a problem where you need to determine whether a given string is a palindrome. A palindrome is a string that reads the same forward and backward when ignoring non-alphanumeric characters and case differences. For instance, “Eva, Ave” is a palindrome, while “race a car” is not.

Solution

function isPalindrome(s: string): boolean {
    // Input validation
    if (!s || s.length === 0) return true;
    
    // Normalize string: lowercase and alphanumeric only
    const normalized = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    
    let left = 0;
    let right = normalized.length - 1;
    
    while (left < right) {
        if (normalized[left] !== normalized[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

Big O Notation Analysis

The isPalindrome function checks whether a given string is a palindrome by using a two pointer technique. Let’s analyze its time and space complexity.

Time Complexity

Since each character in the string is processed at most once, the overall time complexity is O(n), where n is the length of the string.

Space Complexity

The function does not use any additional space that grows with the input size, so the space complexity is O(1).

Brute Force vs Two Pointers

The two pointers technique often transforms a quadratic solution into a linear one, making it significantly more efficient for large datasets.

Two Pointers Variations

1. Opposite Direction: Start from both ends and move toward center (palindrome check, two sum in sorted array)
2. Same Direction: Both pointers move forward at different speeds (slow/fast pointers, remove duplicates)
3. Sliding Window: Dynamic window size based on conditions (longest substring, minimum window)

Common Two Pointers Problems

Here are some classic problems that benefit from the two pointers technique:

1. Two Sum (Sorted Array): Given a sorted array, find two numbers that add up to a target value
2. Remove Duplicates: Remove duplicates from a sorted array in-place while maintaining order
3. Container With Most Water: Find two lines that together with the x-axis form a container holding the most water
4. Valid Palindrome: Check if a string reads the same forward and backward ignoring non-alphanumeric characters

Implementation Tips

Do:

• Ensure your data is sorted when the algorithm requires it
• Handle edge cases (empty arrays, single elements)
• Use clear variable names (left/right or start/end)
• Validate input before processing

Avoid:

• Infinite loops - always ensure pointers move toward termination
• Off-by-one errors with boundary conditions
• Forgetting to handle duplicate values when needed

Conclusion

The two pointers technique is a powerful algorithmic pattern that can dramatically improve the efficiency of your solutions. By understanding when and how to apply this technique, you’ll be well-equipped to tackle a wide range of coding interview problems and real-world optimization challenges.

Next Steps

Ready to practice? Try solving these problems using the two pointers technique:

• Two Sum II (LeetCode 167)
• Valid Palindrome (LeetCode 125)
• Container With Most Water (LeetCode 11)
• Remove Duplicates (LeetCode 26)

Have questions or want to discuss other coding patterns? Feel free to reach out!