Two-Pointer Technique for Sorted Arrays and Strings

The Two-Pointer Technique: An Overview

At its core, the two-pointer technique involves using two integer indices (the "pointers") to traverse a data structure, typically an array or a string. By moving these pointers according to specific conditions, we can efficiently process the data and find a solution in a single pass.

There are a few common variations, but today we will focus on the Opposite Ends pattern. In this pattern, we initialize one pointer at the beginning of the data structure and another at the end. Then, we move them toward each other until they meet or cross.

To get a formal introduction to this pattern and see a generic template in Java, let's turn to a helpful article.

Application 1: Two Sum on a Sorted Array

Let's apply this pattern to a classic interview problem: Two Sum. The problem is as follows: Given an array of sorted integers, find the indices of two numbers that add up to a specific target value.

A brute-force approach would be to use nested loops to check every possible pair of numbers. As you know from our complexity lessons, this would result in an $O(n^2)$ time complexity. We can do much better. Since the array is sorted, it's a perfect candidate for the two-pointer technique.

The following video provides an excellent walkthrough, starting from the brute-force idea and progressively optimizing it to the linear-time two-pointer solution. This will help you understand why the two-pointer approach is so effective.

As the video demonstrated, the logic is elegant and efficient:

1. Initialize a left pointer at index 0 and a right pointer at nums.length - 1.
2. Calculate the sum: currentSum = nums[left] + nums[right].
3. If currentSum equals the target, you've found the solution.
4. If currentSum is less than the target, you need a larger sum. Since the array is sorted, the only way to achieve this is by moving the left pointer to the right (left++).
5. If currentSum is greater than the target, you need a smaller sum. Move the right pointer to the left (right--).
6. Repeat this process until left and right meet. If they meet without finding a solution, no such pair exists.

The image below visualizes this exact process.

Now, let's look at a clean Java implementation of this logic.

By using this technique, we've reduced the time complexity from $O(n^2)$ to $O(n)$, as we only make a single pass through the array. The space complexity is $O(1)$ since we only use a few variables to store the pointers.

Application 2: Valid Palindrome

The two-pointer technique isn't limited to sorted number arrays; it's also highly effective for string manipulation problems. Let's consider another classic: Valid Palindrome. The task is to check if a given string is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters.

For example, "A man, a plan, a canal: Panama" should return true because after cleaning, it becomes "amanaplanacanalpanama", which reads the same forwards and backwards.

The approach is straightforward:

1. First, "clean" the input string by converting it to lowercase and removing any characters that are not letters or numbers. As a Java developer, you can achieve this using a StringBuilder or regex.
2. Once you have the cleaned string, apply the two-pointer pattern. Place a left pointer at the start and a right pointer at the end.
3. Compare the characters at the left and right pointers. If they are ever not the same, the string is not a palindrome.
4. If the characters match, move the pointers one step closer to the center (left++, right--) and repeat until they meet.

Let's examine a practical implementation.

This solution has a time complexity of $O(n)$, where $n$ is the length of the string, because both the cleaning process and the two-pointer check are linear operations. The space complexity is $O(n)$ due to the storage needed for the cleaned string.

Conclusion

In this lesson, you've added a fundamental algorithmic pattern to your problem-solving toolkit. The two-pointer technique is a prime example of how choosing the right algorithm can lead to significant performance improvements—a skill that is heavily tested in SDE interviews.

Here are the key takeaways:

• The two-pointer technique uses two indices to traverse a data structure, often in a single pass.
• The Opposite Ends pattern is highly effective for problems on sorted arrays and strings, where you need to find pairs or check for symmetry.
• It can reduce time complexity from a brute-force $O(n^2)$ to an optimal $O(n)$.
• The core logic for sorted arrays involves adjusting pointers based on whether the current pair's property (like a sum) is too small or too large.
• The core logic for strings often involves checking for symmetrical properties by moving inward from both ends.

We've only scratched the surface of what two pointers can do. In our next lesson, we will explore another powerful variation of this idea: the sliding window technique, which is excellent for finding optimal subarrays or substrings.

To solidify your understanding, I recommend practicing with the "Beginner Level" problems listed in the "Practice Problems" section of the Two Pointer Technique: Mastering the Opposite Ends Pattern article you've been reading.