The two pointers technique is a powerful strategy used to solve problems on arrays and strings efficiently. It involves using two indices that move toward or away from each other based on certain conditions. This approach reduces the need for nested loops and is particularly effective for searching, sorting, and comparing elements in linear time.
For example, to check if a sorted array contains a pair that sums to a target, place one pointer at the start and the other at the end.
Move them based on whether their sum is too high or too low. This method transforms what could be an O(n²) problem into O(n).
The 2 pointers technique is a versatile pattern often used to reduce time complexity from quadratic to linear. It is particularly useful for solving problems involving sorted arrays, partitions, or paired comparisons.
You position two pointers—either at opposite ends or both starting from one side—and move them based on specific conditions. This allows you to examine pairs of elements without checking every combination.
By narrowing the search space intelligently, this method offers clean and fast solutions to problems that otherwise require nested loops. It’s a go-to technique for optimizing brute-force approaches.
Mastering the 2 pointers pattern equips you with a simple yet powerful approach to tackle a wide range of interview problems and real-world scenarios involving arrays and strings.
The Two Pointers algorithm is a widely used technique in array-based problems that involves managing two indices—commonly referred to as pointers—within a data structure. These pointers are used to scan or traverse the array in a coordinated manner, optimizing the computation of certain conditions or transformations. A notable and powerful variation of this technique is known as the squeeze pattern.
In the squeeze pattern, one pointer is initialized at the beginning of the array, and the other is set at the end. These pointers then move toward each other, progressively narrowing the section of the array being examined. This bidirectional traversal allows the algorithm to simultaneously consider both ends of the array, which is especially useful when the elements are sorted or when comparisons across distant positions are required.
While the Two Pointers method can take other forms—such as in the sliding window technique, where both pointers move in the same direction—this explanation focuses on the squeeze pattern. The primary benefit of using this approach lies in its efficiency. By eliminating the need to perform redundant operations or rely on slower sorting algorithms, the squeeze pattern can reduce the overall time complexity of a problem from O(n log n) to a much faster O(n).
A classic example that demonstrates the efficiency of the Two Pointers squeeze pattern is the Squares of a Sorted Array problem. The task is to take a sorted array of integers, square each number, and return a new array of these squares, also sorted in non-decreasing order. The initial instinct might be to square each number and then sort the new array, which would result in a O(n log n) time complexity due to the sorting step.
However, a key observation can dramatically improve this. In a sorted array, the elements with the largest absolute values—which produce the largest squares—are always located at the ends of the array. This characteristic allows us to leverage the squeeze pattern to efficiently construct the result.
To apply the Two Pointers squeeze approach, we begin by initializing two pointers: L at index 0 (the start of the array) and R at the last index (the end of the array). We also prepare an empty result array to store the squared values.
A loop is executed while the left pointer is less than or equal to the right pointer (L ≤ R). At each step, we compare the absolute values of the elements at the current positions of the left and right pointers. The square of the larger absolute value is guaranteed to be the largest remaining square in the array. This square is then appended to the end of the result array. Following this, we move the pointer that pointed to the larger absolute value inward—L is incremented or R is decremented.
This process continues until the pointers cross, ensuring that all elements have been processed exactly once. Since the largest squares are added to the result array first, the result ends up in descending order.
Because the result array has been constructed in reverse order (largest to smallest), a final step is required to produce the desired non-decreasing order. This is achieved by simply reversing the result array. The reversal is an O(n) operation and completes the transformation efficiently without altering the time complexity of the algorithm.
The Two Pointers solution runs in O(n) time. Each element in the array is examined exactly once during the pointer traversal, and the reversal of the result array is also performed in linear time. Thus, the algorithm is significantly more efficient than the brute-force sorting approach.
Regarding space complexity, the solution uses a new array to store the squared values. While this is technically additional memory, it is generally not counted as extra space in complexity analysis when the output itself must be returned. For this reason, the space complexity is often referred to as O(1) auxiliary space, or O(n) if we include the result as extra.
The Two Pointers algorithm, particularly the squeeze pattern, offers a powerful method for solving problems that involve comparisons from both ends of a sorted array. By leveraging this approach, it is possible to reduce time complexity from O(n log n) to O(n), enabling faster and more scalable solutions. The “Squares of a Sorted Array” problem provides a clear example of how this algorithm can be effectively applied, making the Two Pointers technique an essential tool in any programmer’s algorithmic toolkit.