Two Pointers Pattern
Overview
The Two Pointers pattern is a technique where two distinct pointers (usually index variables) iterate over a data structure (like an array or a string) in tandem. Typically, one starts at the beginning and the other at the end, and they move towards each other. This is incredibly powerful for optimizing O(N^2) brute-force nested loops down to O(N) linear time, specifically when dealing with sorted arrays or palindromes.
Syntax
Instead of creating a new array (O(N) space), we use two pointers to swap elements in place, achieving O(N) Time and O(1) Space.
public void reverse(char[] s) {
int left = 0;
int right = s.length - 1;
// Pointers move towards the center
while (left < right) {
// Swap elements
char temp = s[left];
s[left] = s[right];
s[right] = temp;
// Move pointers inward
left++;
right--;
}
}Because the array is sorted, we can mathematically guarantee which pointer to move based on whether the sum is too high or too low. This avoids an O(N^2) nested loop.
// Given a SORTED array, find two numbers that add up to a target
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left, right};
} else if (sum < target) {
left++; // Need a larger number, move left pointer right
} else {
right--; // Need a smaller number, move right pointer left
}
}
return new int[]{-1, -1};
}Common Pitfalls
- Using Two Pointers on an Unsorted array. The math completely falls apart if the array isn't sorted.
- Forgetting to check `left < right` inside inner while loops when skipping characters, leading to OutOfBoundsExceptions.
Interview Tips
- The Two Pointers pattern is a silver bullet for optimizing O(N^2) loops down to O(N) when dealing with sorted arrays or strings.
Real-World Example
Detecting Palindromes or filtering out invalid characters from a string during text parsing.
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// Skip non-alphanumeric characters
if (!Character.isLetterOrDigit(s.charAt(left))) { left++; continue; }
if (!Character.isLetterOrDigit(s.charAt(right))) { right--; continue; }
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++; right--;
}
return true;
}