Use two pointers to iterate through an array or list, often used to find pairs or elements that meet specific criteria.

The algorithm basically uses the fact that the input array is sorted.

Imagine you have a sorted list of numbers and you want to find two numbers that add up to a specific target sum. Here’s how the two-pointer technique works:

1. Two pointers: Imagine having two markers, one at the beginning (left pointer) and another at the end (right pointer) of the sorted array.
2. Check the sum: Add the values pointed to by the left and right pointers.
3. Did target reach?
   • If the sum is equal to the target, then you’ve found a pair! (A[left pointer] + A[right pointer] = target)
   • If the sum is less than the target, the number you’re looking for must be bigger. So move the left pointer one step forward (towards larger numbers).
   • If the sum is greater than the target, the number you’re looking for must be smaller. So move the right pointer one step backward (towards smaller numbers).
4. Repeat steps 2 and 3 until you find a pair that adds up to the target or you exhaust all possibilities (pointers meet in the middle).

Example Time:

• Input: nums = [1, 2, 9, 14, 26], target = 16
• Output: [1, 3]

Let’s implement this with some Java Code:

public int[] twoSum(int[] nums, int target) {

        int l=0, r=nums.length-1;

        while(nums[l]+nums[r] != target)
        {
            if(nums[l]+nums[r] <target)
            l++;
            else
            r--;
        }
        return new int[]{l,r};
    }

 

This technique works because the array is sorted. As you move the pointers, you’re guaranteed to be checking larger or smaller numbers based on the sum you get.

• Efficient: It’s faster than checking every single pair of numbers in the array.
• Easy to implement: The logic is straightforward and requires minimal coding complexity.

Time Complexity:  O(n log n) (As sort function is used)

Auxiliary Space: O(1), since no extra space has been taken.

Now the most important part to practice this pattern. Below are some problems which I found on LeetCode and GFG:

• Remove Duplicates from Sorted Array
• Two Sum II – Input array is sorted
• Reverse Words in a String II
• Rotate Array
• Valid Palindrome
• Container With Most Water
• Product of Array Except Self
• Find the closest pair from two sorted arrays
• Find the pair in array whose sum is closest to x
• Find all triplets with zero sum
• Find a triplet that sum to a given value
• Find a triplet such that sum of two equals to third element
• Find four elements that sum to a given value