Learn
Two Pointers Technique
The Two Pointers technique uses two indices moving through a data structure to solve problems efficiently. For sorted arrays, you often use one pointer at each end moving toward the center.
To find a pair with a target sum in a sorted array, you compare the sum at both pointers with the target.
function twoSum(arr, n, target):
left = 0
right = n - 1
while left < right:
sum = arr[left] + arr[right]
if sum == target:
return (left, right)
else if sum < target:
left = left + 1
else:
right = right - 1
return (-1, -1)
Why it works: In a sorted array, if the current sum is too small, you need a larger value. The only way to get a larger sum is to move the left pointer right. Similarly, if the sum is too large, you move the right pointer left.
Counting pairs: To count all pairs with a given sum, you handle duplicates by counting occurrences when pointers meet.
Applications: You use two pointers for pair sum problems, container with most water, removing duplicates, merging sorted arrays, and palindrome checking.
Time complexity: because each pointer moves at most times.
Space complexity: using only two index variables.