Two Pointer Technique
Definition
The Two Pointer technique uses two distinct indices (pointers) to traverse an array (usually sorted) or string. Typically, one pointer starts at the beginning (left) and the other at the end (right), and they move toward each other based on specific conditions. 
How it Works
- Initialize: Set left = 0 and right = n-1.
- Loop: While left < right:
- Check a condition (e.g., is the sum too big?).
- Move the left pointer forward or the right pointer backward to adjust.
Real-World Analogy
Folding a Sheet: If you want to find the middle of a bedsheet or fold it, you grab both corners (left and right) and bring them together until they meet in the center.
Example
Problem: Find two numbers in a sorted array that add up to a target (Target = 10). Array: [2, 4, 6, 8, 10]
- L(2) + R(10) = 12. Too big! We need a smaller sum, so move R down.
- L(2) + R(8) = 10. Match!
Code Example
PythonJavaCC++
# Two Pointer Technique for sorted array
def two_sum_sorted(arr, target):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # move left pointer right
else:
right -= 1 # move right pointer left
return None
print(two_sum_sorted([2, 4, 6, 8, 10], 10))
# Output: [0, 3]
public class TwoSumSorted {
static int[] twoSumSorted(int arr[], int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return new int[]{left, right};
else if (sum < target)
left++;
else
right--;
}
return null;
}
public static void main(String[] args) {
int arr[] = {2,4,6,8,10};
int result[] = twoSumSorted(arr, 10);
System.out.println(result[0] + " " + result[1]);
}
}
#include <stdio.h>
void twoSumSorted(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
printf("[%d, %d]\n", left, right);
return;
}
else if (sum < target)
left++;
else
right--;
}
printf("No pair found\n");
}
int main() {
int arr[] = {2,4,6,8,10};
twoSumSorted(arr, 5, 10);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
vector<int> twoSumSorted(vector<int> arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return {left, right};
else if (sum < target)
left++;
else
right--;
}
return {};
}
int main() {
vector<int> arr = {2,4,6,8,10};
vector<int> result = twoSumSorted(arr,10);
cout << "[" << result[0] << ", " << result[1] << "]";
return 0;
}
Complexity Analysis
- Time Complexity: O(N). We touch every element at most once.
- Space Complexity: O(1).
Use Cases
- Two Sum: Finding pairs in a sorted array.
- Reversing: Reversing an array or string in-place.
- Palindrome Check: Checking if a string reads the same forwards and backwards.