Two-pointer Summary

The two-pointer technique is a versatile and efficient strategy commonly used in solving problems on arrays, strings, linked lists, and other data structures. This blog summarizes key LeetCode problems where the two-pointer method not only simplifies the approach but also optimizes performance, especially compared to brute-force solutions.

Arrays: Optimizing Element Removal

In 27. Remove Element, the task is to remove specific elements from an array in place. Using naive methods like repeatedly calling deletion operations can result in complexity because every removal shifts elements in the array. The two-pointer technique offers a more efficient alternative:

Fast and Slow Pointers

The fast and slow pointer variation of the two-pointer method works as follows:

Fast Pointer: Traverses the array to find elements that are not equal to the target value.
Slow Pointer: Marks the position where non-target elements should be placed.

By iterating through the array once, the fast pointer identifies elements to retain, and the slow pointer updates their positions. This method operates in time with space and ensures the relative order of elements remains unchanged.

Left and Right Pointers

Another variation employs left and right pointers:

Left Pointer: Starts from the beginning and moves forward to find elements equal to the target value.
Right Pointer: Starts from the end and moves backward to find elements not equal to the target value.

When the two pointers meet, the process ends. This variation is particularly useful when the relative order of elements does not need to be preserved. Both methods achieve time complexity and space complexity, showcasing the flexibility of the two-pointer technique.

Strings: Reversal and Space Optimization

Reverse String

In 344. Reverse String, the goal is to reverse a string in place. Using two pointers, one starting from the beginning and the other from the end, we swap characters while moving the pointers toward the center. This approach achieves complexity and adheres to the in-place constraint effectively.

Reverse Words in a String

In 151. Reverse Words in a String, redundant spaces must be removed, and the words reversed. Employing two pointers, one can clean up spaces while reversing the words in a single pass, avoiding the inefficiencies of naive solutions that repeatedly shift elements. This method ensures time complexity, even when dealing with substantial input strings.

Linked Lists: Reversals and Cycle Detection

Reverse Linked List

In 206. Reverse Linked List, the two-pointer technique is used to reverse the direction of next pointers within the list. Starting with prev as None and curr pointing to the head, the pointers are updated iteratively to reverse the list. This concise yet powerful approach operates in time and space.

Detect Cycle in a Linked List

In 142. Linked List Cycle II, two pointers (slow and fast) traverse the list at different speeds. If a cycle exists, they will eventually meet. Determining the entry point of the cycle involves simple mathematical reasoning based on their meeting point. The efficiency and elegance of this approach make it a staple interview question.

N-Sum Problems: Efficient Searching

Two-Sum, Three-Sum, and Beyond

In 15. 3Sum, while hash maps work well for two-sum problems, they struggle with larger sets due to difficulties in deduplication and pruning. The two-pointer method excels in -sum problems (e.g., 3Sum, 4Sum) by reducing the brute-force complexity to for 3Sum and for 4Sum.

For 3Sum, after sorting the array, one pointer iterates through the list, while the other two pointers converge from opposite ends. This allows for efficient pruning and avoids excessive comparisons. The same principle extends naturally to 18. 4Sum, with one additional layer of iteration.

Key Takeaways

Efficiency: The two-pointer technique optimizes performance by performing tasks like element removal, space cleanup, and subset search in or , compared to or higher for naive approaches.
Versatility: Applicable across arrays, strings, and linked lists, the technique adapts well to various constraints and problem domains.
Readability: Two-pointer solutions often result in concise and maintainable code, a significant advantage during coding interviews.

To master this technique, revisit the linked problems, reflect on the methodology, and observe how the pointers interact. Understanding these patterns will prepare you to tackle complex variations with confidence.