Two-Pointer Technique for Arrays and Strings

1. What is the Two-Pointer Technique?

At its core, the two-pointer technique involves using two integer variables—pointers—that move through a data structure, typically an array or string. By coordinating their movement, we can process data or find elements that satisfy a condition much more efficiently than with nested loops.

There are a few common ways this pattern is applied, which you'll see throughout this module. To get a high-level overview of these variations, let's start with a short, conceptual video.

As the video explained, our focus today is on the converging pointers (or "opposite ends") pattern. This is where we initialize one pointer at the beginning of the data structure and another at the end, then move them toward each other until they meet or cross.

2. The Canonical Example: Two Sum in a Sorted Array

The most classic application of the converging pointers pattern is solving the "Two Sum" problem on a sorted array. This problem is a fundamental building block for many harder interview questions.

Problem: Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers.

A brute-force approach would use nested loops to check every possible pair, resulting in an O($n^2$) time complexity. We can do much better.

The key insight comes from the array being sorted.

1. Initialize a left pointer at index 0 and a right pointer at the last index.
2. Calculate the current_sum = numbers[left] + numbers[right].
3. Compare current_sum with the target:
   • If current_sum < target, we need a larger sum. Since the array is sorted, we must move our left pointer one step to the right to include a larger number.
   • If current_sum > target, we need a smaller sum. We must move our right pointer one step to the left to include a smaller number.
   • If current_sum == target, we have found our pair!

This process efficiently eliminates possibilities with each step, allowing us to find the solution in a single pass.

To see this implemented in code and explained in detail, please read the following section from the CodeBeast article.

This O($n$) time and O(1) space solution is exactly what interviewers are looking for.

3. Pattern Recognition: When Should You Think "Two Pointers"?

Recognizing when to apply a pattern is just as important as knowing how to implement it. So, what are the tell-tale signs that a problem might be solvable with the two-pointer technique?

Here are some common clues:

• The input is a sorted array or string.
• The problem involves finding a pair of elements that satisfy a certain condition (e.g., a target sum).
• A brute-force solution would involve nested loops to compare every pair of elements.
• The problem requires an in-place modification or has a strict O(1) space complexity constraint.

The next video gives more examples and summarizes these clues effectively.

As a supplement, the CodeBeast article you read earlier also has a fantastic section on this topic. It's worth a quick review to solidify these concepts.

4. Other Applications of Converging Pointers

The same "opposite ends" logic applies to many other problems.

Valid Palindrome (Recap)

In the last lesson, we checked if a string is a palindrome. This is a perfect example of the converging pointers pattern.

1. Pointers start at the beginning and end of the string.
2. They move inward, skipping non-alphanumeric characters.
3. At each step, they check if the characters are equal (ignoring case). If not, it's not a palindrome.
4. If the pointers meet or cross without finding a mismatch, it is a palindrome.

Squares of a Sorted Array

Here's a less obvious but common interview problem that can be optimized with two pointers.

Problem: Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example: Input: nums = [-4,-1,0,3,10], Output: [0,1,9,16,100]

A simple approach is to square every element and then sort the resulting array. This would be O(n log n). Can we do it in O(n)?

Yes! The largest squared values will come from the numbers at the ends of the original array (because of negative numbers). For [-4, -1, 0, 3, 10], the largest square could be (-4)^2 = 16 or 10^2 = 100.

This insight leads to a two-pointer solution:

1. Initialize left = 0, right = len(nums) - 1.
2. Create a result array of the same size, filled with zeros.
3. Use a third pointer, write_pos, starting from the end of the result array (len(nums) - 1).
4. While left <= right:
   • Compare abs(nums[left]) and abs(nums[right]).
   • Whichever absolute value is larger will produce the larger square. Place this square at result[write_pos].
   • Move the pointer (left or right) that corresponded to the larger absolute value.
   • Decrement write_pos.
5. Return the result array.

Conclusion

You've now formally learned one of the most fundamental interview patterns. By replacing nested loops with two intelligently moving pointers, you can write clean, efficient, and optimal code.

Key Takeaways:

• The Two-Pointer Technique is a high-ROI pattern for optimizing problems on sequential data structures like arrays and strings, typically from O($n^2$) to O($n$).
• The Converging (Opposite Ends) Pattern is ideal for sorted arrays where you need to find pairs satisfying a condition (like a target sum) or for problems involving symmetry (like palindromes).
• Pattern recognition is crucial: Look for sorted data, pair-finding requirements, and opportunities to avoid nested loops.

In our next lesson, we will explore a different variation of this pattern: the fast and slow pointer technique. It's another powerful tool, used most famously to solve problems involving cycles and midpoints in linked lists.