Mastering the Two-Pointer Technique

Welcome to the first lesson of your program. We're kicking off the "Arrays, Strings & Hashing Patterns" module by diving into a fundamental and highly efficient algorithmic pattern: the two-pointer technique.

Mastering this technique is a crucial first step in your interview preparation. It frequently appears in coding challenges because it demonstrates your ability to transform a slow, brute-force solution into a fast, optimized one—a skill highly valued in senior engineering roles. In this lesson, you'll learn to identify problems that fit this pattern and apply it to solve common questions involving sorted arrays and strings.

The Core Idea: Optimizing Traversal

At its heart, the two-pointer technique is a method for optimizing problems that would otherwise require nested loops. A naive approach to finding pairs of elements in an array that satisfy a certain condition often involves a nested loop structure, leading to a time complexity of $O(n^2)$. For large datasets, this is often too slow.

The two-pointer technique allows us to solve many of these problems in a single pass, achieving a linear time complexity of $O(n)$ and often using constant extra space, $O(1)$.

There are two main variations of this pattern, which we'll explore in detail:

1. Opposite Direction Pointers: Two pointers start at opposite ends of the data structure (e.g., an array) and move toward each other.
2. Same Direction Pointers: Two pointers start at or near the beginning and move in the same direction, often at different speeds (a "slow" and "fast" pointer).

Let's start by building a solid theoretical foundation for both.

Pattern 1: Opposite Direction Pointers

This is arguably the most common variant of the two-pointer technique. It's particularly effective when working with sorted arrays.

The strategy is as follows:

• Initialize a left pointer at the beginning of the array (index 0).
• Initialize a right pointer at the end of the array (index n-1).
• In a loop, analyze the elements at arr[left] and arr[right].
• Based on a specific condition, you'll move one of the pointers inward (left++ or right--), effectively shrinking the search window until the pointers meet or cross.

The power of this approach comes from the sorted nature of the array. By comparing the sum (or another property) of the elements at the pointers to a target, you can make an intelligent decision about which part of the array to discard. If your current sum is too small, you know you must increase it by moving the left pointer to a larger value. If it's too large, you must decrease it by moving the right pointer to a smaller value.

Classic Problem: Two Sum on a Sorted Array

Let's apply this pattern to a classic interview problem: Given a sorted array of integers, find two numbers that add up to a specific target.

Imagine the array [1, 2, 4, 6] and a target sum of 6.

1. left points to 1, right points to 6. Sum = 1 + 6 = 7.
   • 7 > 6 (target), so the sum is too high. We need a smaller number. We move the right pointer to the left.
2. left points to 1, right points to 4. Sum = 1 + 4 = 5.
   • 5 < 6 (target), so the sum is too low. We need a larger number. We move the left pointer to the right.
3. left points to 2, right points to 4. Sum = 2 + 4 = 6.
   • 6 == 6 (target). We have found the pair.

Notice how in each step, we eliminate either the current left or right element and all potential pairs involving it. This guarantees we find the solution in a single pass.

Since your background is in Go, let's walk through a detailed implementation.

Pattern 2: Same Direction Pointers

In this pattern, both pointers (often called slow and fast) start at or near the beginning of the array and move in the same direction. The fast pointer typically iterates through the elements, while the slow pointer only advances when a certain condition is met.

This pattern is excellent for problems involving the removal of duplicates, or any situation where you need to process an array and build a new, modified version of it in-place. The slow pointer effectively marks the end of the valid, processed section of the array.

Classic Problem: Remove Duplicates from a Sorted Array

Let's consider the problem: Given a sorted array, remove the duplicates in-place such that each unique element appears only once and return the new length of the modified array.

For an array like [0, 0, 1, 1, 1, 2, 2, 3], the goal is to modify it to [0, 1, 2, 3, ...] and return 4.

The logic is as follows:

• Initialize a slow pointer (let's call it insert_idx) at index 1, as the first element is always unique.
• Initialize a fast pointer to iterate from the second element (index 1) to the end.
• At each step, compare arr[fast] with the previous element arr[fast - 1].
• If arr[fast] is different from arr[fast - 1], it's a new unique element. We copy it to the position of our slow pointer: arr[insert_idx] = arr[fast], and then advance the slow pointer: insert_idx++.
• If arr[fast] is the same, it's a duplicate. We do nothing but advance the fast pointer.

Here's how you could implement this in Go:

// removeDuplicates modifies the array in-place and returns the number of unique elements.
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    // `insertIdx` is the "slow" pointer. It marks the position
    // where the next unique element should be placed.
    insertIdx := 1

    // `i` is the "fast" pointer. It scans ahead to find unique elements.
    for i := 1; i < len(nums); i++ {
        // If the current element is different from the previous one, it's unique.
        if nums[i] != nums[i-1] {
            // Place the unique element at the insertIdx position.
            nums[insertIdx] = nums[i]
            // Move the slow pointer forward.
            insertIdx++
        }
    }

    return insertIdx
}

The video below provides a great visual walkthrough of both the "Two Sum" and "Remove Duplicates" problems.

Application to Strings: Valid Palindrome

The two-pointer technique isn't limited to arrays of numbers; it's also very effective for string manipulation. A classic example is checking if a string is a palindrome.

The problem: A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forwards and backward.

This is a perfect fit for the opposite direction pattern.

1. Preprocessing: First, clean the string. Create a new string or a slice of runes containing only the lowercase alphanumeric characters from the original string.
2. Two Pointers: Initialize left = 0 and right = len(cleaned_string) - 1.
3. Comparison: In a loop (while left < right), compare the characters at the left and right pointers.
   • If they are not equal at any point, the string is not a palindrome, and you can return false immediately.
   • If they are equal, move the pointers inward: left++, right--.
4. Result: If the loop completes without finding any mismatches, the string is a palindrome.

Here is a sample implementation in Go, leveraging the unicode package for robust character checking.

import "unicode"

func isPalindrome(s string) bool {
    // Preprocessing Step: Filter the string to keep only alphanumeric characters.
    // We can do this with two pointers on the original string's byte slice,
    // or build a new slice. Let's build a new slice for clarity.
    var filtered []rune
    for _, r := range s {
        if unicode.IsLetter(r) || unicode.IsDigit(r) {
            filtered = append(filtered, unicode.ToLower(r))
        }
    }

    // Two-Pointer Check Step
    left, right := 0, len(filtered)-1
    for left < right {
        if filtered[left] != filtered[right] {
            return false
        }
        left++
        right--
    }

    return true
}

The video resource you reviewed earlier also has a great section that walks through this exact problem.

Conclusion

In this lesson, you've been introduced to the two-pointer technique, a powerful tool for optimizing array and string algorithms. We've covered the core theory and applied it to several classic interview problems.

Key Takeaways:

• The two-pointer technique is a method to transform O(n²) brute-force solutions into O(n) linear-time solutions.
• Opposite direction pointers are ideal for searching for pairs in sorted arrays or for problems with symmetrical properties like palindromes. The key is to shrink the search space from both ends.
• Same direction pointers (slow/fast) are effective for in-place modifications, like removing duplicates, where one pointer tracks the write position and the other scans ahead.
• Identifying the correct condition for moving the pointers is the most crucial part of solving these problems.

In our next lesson, we will explore a powerful extension of the same-direction pointer pattern known as the sliding window technique. It's used to solve a different class of problems, typically those asking for the "longest," "shortest," or "best" subarray or substring that satisfies a given condition.