Two Pointers Pattern
Overview
The Two Pointers pattern is a highly efficient algorithmic technique used primarily on arrays and strings. Instead of using a single loop variable (i) or nested loops (i and j testing every combination), you use two integer variables that act as 'pointers' to different indices in the data.
The most classic variation is Opposite Direction pointers: one pointer starts at the beginning (left = 0) and one starts at the end (right = arr.length - 1). They move towards each other until they meet. This is the foundation of algorithms for reversing strings, checking palindromes, and solving 'Two Sum' on sorted arrays.
The second variation is Same Direction pointers (often called 'Fast and Slow' pointers), where both start at 0 but move at different speeds.
The beauty of this pattern is that it almost always reduces an O(N^2) naive nested-loop solution into a blazing fast O(N) solution.
Syntax
public class TwoPointers {
// 1. Opposite Direction Pattern
public static void reverseArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
// Loop runs until the pointers crash into each other
while (left < right) {
// Swap the elements at the pointers
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
// Move pointers inward!
left++;
right--;
}
}
// 2. Finding a Target Sum in a SORTED Array (Two Sum II)
public static boolean hasTargetSum(int[] sortedArr, int target) {
int left = 0;
int right = sortedArr.length - 1;
while (left < right) {
int currentSum = sortedArr[left] + sortedArr[right];
if (currentSum == target) {
return true; // Found the pair!
} else if (currentSum < target) {
// Sum is too small. We need a bigger number.
// Since array is sorted, moving left pointer to the right increases sum.
left++;
} else {
// Sum is too big. We need a smaller number.
right--;
}
}
return false;
}
}Common Pitfalls
- Using
left <= rightwhen swapping elements. If you use<=in an array reversal, whenleft == right(the middle element of an odd-length array), the algorithm swaps the element with itself. While harmless, it's an unnecessary operation.left < rightis cleaner. - Applying the Two Sum pointer logic to an UNSORTED array. The logic
if (sum < target) left++strictly relies on the array being sorted in ascending order. If the array is unsorted, moving the left pointer doesn't guarantee a larger number. For unsorted arrays, you must use a HashMap instead. - Infinite loops due to forgotten increments. If you use a
whileloop and forget to writeleft++orright--in one of yourif-elsebranches, the pointers will never move, freezing the program.
Interview Questions
Initialize left at 0 and right at str.length() - 1. While left < right, check if str.charAt(left) == str.charAt(right). If they don't match, return false immediately. Otherwise, left++ and right--. If the loop finishes, return true. This takes O(N) time and O(1) space.
Also known as the Tortoise and Hare algorithm. It uses two pointers moving in the same direction at different speeds. It is famous for detecting cycles in a Linked List (if the fast pointer laps the slow pointer, a cycle exists) or finding the middle of a Linked List in one pass.
Real-World Example
When analyzing sensor telemetry data (like temperatures sorted by time), if an engineer wants to find two specific timestamps where the combined temperature difference exactly matches a specific threshold, a two-pointer approach sweeps through the millions of data points in linear time instantly.
// Check if a word is a palindrome, ignoring non-alphanumeric chars
public boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
return false;
}
i++; j--;
}
return true;
}Check Your Knowledge
Test your understanding of Two Pointers Pattern with these quick questions.