DSA: Two Pointers Pattern

6 min read5k
#DSA#InterviewPrep

Solution to Last Week's Challenge

Last week's problem was: DSA: HashMap Patterns for Interviews

The optimal solution uses dsa: hashmap patterns for interviews pattern with careful state management.

Complexity Analysis:

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

In the toolkit of a senior engineer, the Two Pointers pattern is often the first line of defense against inefficient $O(N^2)$ algorithms. When dealing with linear data structures like arrays or linked lists, we frequently encounter problems where we need to compare elements, find pairs, or detect cycles. While a naive nested loop approach is easy to implement, it rarely scales. The Two Pointers pattern allows us to process data in a single pass, often reducing the time complexity to $O(N)$ and the space complexity to $O(1)$.

In real-world systems, this efficiency is critical. Whether you are optimizing a memory-constrained embedded system or a high-throughput data streaming pipeline, reducing unnecessary iterations directly translates to lower latency and reduced compute costs. During technical interviews at companies like Google or Meta, the ability to recognize when a problem can be solved with Two Pointers—especially when it involves sorted data—is a key signal of algorithmic maturity.

Theory

The core concept of the Two Pointers pattern is the use of two indices (or pointers) that traverse the data structure in a coordinated manner. Unlike a standard loop that uses one index, this pattern uses the relative positions of two indices to narrow down the search space or perform comparisons without redundant checks.

There are three primary variations of this pattern:

  1. Opposite Ends: Pointers start at the beginning and end, moving toward each other. This is common in sorted arrays or palindrome checks.
  2. Fast and Slow (Hare and Tortoise): Pointers move at different speeds. This is the gold standard for detecting cycles in linked lists or finding the midpoint.
  3. Same Direction: Both pointers start at the beginning but move based on specific conditions, often used for "in-place" array modifications.

Pattern Visualization

To solve a problem using Two Pointers, you must define the condition that triggers a pointer movement. For a sorted array search, the logic typically follows this flow:

Implementation

Let's look at the "Two Sum II" problem: Given a sorted array, find two numbers that add up to a specific target.

Brute Force Approach

The naive approach uses nested loops to check every possible pair.

python
def two_sum_brute(numbers, target):
    # Time Complexity: O(n^2)
    # Space Complexity: O(1)
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

Optimized Two Pointers Approach

Since the array is sorted, we can use pointers at both ends to converge on the target.

python
def two_sum_optimized(numbers, target):
    # Time Complexity: O(n) - Single pass
    # Space Complexity: O(1) - No extra storage
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1  # Need a larger sum
        else:
            right -= 1 # Need a smaller sum
            
    return []

Complexity Analysis Table

ApproachTime ComplexitySpace ComplexityBest For
Brute Force$O(N^2)$$O(1)$Small datasets ($N < 100$)
Hash Map$O(N)$$O(N)$Unsorted data, extra memory available
Two Pointers$O(N)$$O(1)$Sorted data, memory-constrained

Common Patterns

1. Fast and Slow Pointers (Cycle Detection)

This is used to detect loops in linked lists. If the fast pointer eventually catches the slow pointer, a cycle exists.

python
def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

2. Same Direction (Remove Duplicates)

Useful for modifying an array in-place to save memory.

python
def remove_duplicates(nums):
    if not nums: return 0
    write_ptr = 1
    for read_ptr in range(1, len(nums)):
        if nums[read_ptr] != nums[read_ptr - 1]:
            nums[write_ptr] = nums[read_ptr]
            write_ptr += 1
    return write_ptr

Practice Problems

The following chart maps common Two Pointer problems by their frequency in FAANG interviews and their relative difficulty.

This Week's Interview Challenge

Problem: Valid Palindrome II

Given a string s, return true if the s can be a palindrome after deleting at most one character from it.

Examples:

  • Input: s = "aba" | Output: true
  • Input: s = "abca" | Output: true (Delete 'c' to get "aba")
  • Input: s = "abc" | Output: false

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

Hints:

  1. Start with the standard Two Pointers approach for a palindrome (left and right ends).
  2. When you encounter a mismatch (s[left] != s[right]), you have two choices: delete the character at left or delete the character at right.
  3. Check if the remaining substring (after either deletion) is a palindrome.
  4. Since you can only delete once, this "branching" logic only happens at most one time.

Template Code:

python
def valid_palindrome(s: str) -> bool:
    # TODO: Implement the Two Pointers logic
    pass

# Submit your solution and check back next week for the detailed answer!

Conclusion

The Two Pointers pattern is a fundamental optimization technique that every engineer should master. Its beauty lies in its simplicity: by just adding one more index, we can often bypass the need for nested loops or expensive auxiliary data structures. When you see a problem involving sorted arrays, linked list traversal, or pair-finding, your first instinct should be to ask: "Can I solve this with Two Pointers?"

Mastering this pattern not only helps you ace the technical interview but also trains you to think about data traversal in a more memory-efficient way.

References