Two Pointers Pattern
The two-pointer technique is an approach used to solve problems on arrays or lists by using two indices (pointers) that move through the data structure, usually from opposite ends or sometimes the same direction, depending on the problem.
Why use two pointers?
1). To reduce the time complexity compared to nested loops (which are O(n²)).
2). To efficiently search for pairs, triplets, or intervals satisfying a certain condition.
3). To avoid extra space usage by working directly on the input array.
Common scenarios for two-pointers:
1). Finding pairs with a sum (Two Sum in sorted array)
2). Removing duplicates or partitioning arrays
3). Merging two sorted arrays
4). Trapping rain water problem
5). Reversing arrays or strings
Two-Pointer Technique Templates
When solving array and string problems efficiently, the two-pointer technique is a powerful approach. Depending on the problem type, it can be applied in two common patterns:
- Opposite Direction Pointers Template
- In this Template, pointers start from opposite ends of the array (one at the beginning, the other at the end).
- The pointers move towards each other based on certain conditions until they meet.
- Common use cases: checking for palindromes, two-sum in sorted arrays, and merging intervals.
- Same Direction Pointers Template
- Here, both pointers start from the same side (often the beginning) and move forward in the same direction.
- One pointer usually lags behind while the other explores ahead.
- Common use cases: Minimum absolute difference in an array and Pairs problems.
In this Template, pointers start from opposite ends of the array (one at the beginning, the other at the end).
In this Template, both pointers start from the same side (often the beginning) and move forward in the same direction.
The Two Sum problem is a classic algorithmic challenge where you are given an array of integers and a target value. The goal is to find two numbers in the array that add up to the target and return their indices.
The Three Sum problem is a classic algorithmic challenge where you are given an array of integers. The goal is to find all unique triplets in the array whose sum equals zero and return them as a list of triplets.
The Four Sum problem is a classic algorithmic challenge where you are given an array of integers. The goal is to find all unique quadruplets in the array whose sum equals zero and return them as a list of quadruplets.
The Container With Most Water problem gives an array of line heights and requires finding two indices that form a container with the maximum possible area based on their heights and distance.
The Valid Palindrome problem takes a string and requires determining whether it reads the same forward and backward after removing non-alphanumeric characters and ignoring letter case.
The Rotate Array problem provides an array and a number k, and requires shifting the array elements to the right by k positions, wrapping elements around to maintain the array’s original size.
The Minimum Absolute Difference problem requires finding the smallest absolute difference between any two elements in the array after evaluating all possible pairs.
The Pairs problem involves identifying all valid pairs in an array that satisfy a given condition, such as having a specific difference. The goal is to efficiently find and return all such qualifying pairs.