Understanding how the two pointers technique achieves linear time for array and string problems
The two pointers technique uses two pointers (indices) that traverse an array or string, typically from opposite ends or both from the start. This technique is efficient for problems involving pairs, palindromes, or sorted arrays.
Common Patterns:
Think of it like two people walking towards each other from opposite ends of a hallway - they meet in the middle, and you only need to check each position once!
Start with two pointers, typically at opposite ends (left = 0, right = n-1) or both at the start (left = 0, right = 0).
Process the elements at both pointer positions, then move the pointers based on some condition (e.g., move left forward if sum is too small, move right backward if sum is too large).
Each element is visited at most once by each pointer. Since pointers move towards each other or in one direction, total operations are O(n):
Instead of nested loops (O(n²)) checking all pairs, two pointers eliminate half the search space at each step, reducing complexity to O(n). This is especially powerful for sorted arrays!
Code Example:
// Two pointers: find two numbers that sum to target - O(n)
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return [left, right]; // Found!
} else if (sum < target) {
left++; // Need larger sum
} else {
right--; // Need smaller sum
}
}
return null; // Not found
}Find two numbers that add up to a target in a sorted array.
Check if a string reads the same forwards and backwards.
Remove duplicates from sorted array in-place.
Find two lines that together form the container with most water.
Calculate how much rainwater can be trapped between bars.
Each pointer visits each element at most once. Since there are two pointers but they move towards each other, the total number of positions checked is at most n.
At each step, you eliminate a portion of the search space:
Two pointers vs nested loops:
| Problem Type | Nested Loops | Two Pointers | Improvement |
|---|---|---|---|
| Find Pair Sum | O(n²) | O(n) | n× faster |
| Check Palindrome | O(n²) | O(n) | n× faster |
| Remove Duplicates | O(n²) | O(n) | n× faster |
| Three Sum | O(n³) | O(n²) | n× faster |
E-commerce sites use two pointers to find product pairs within a price range. Instead of checking all combinations (O(n²)), two pointers find matches in O(n) time.
Checking if text is a palindrome (reads same forwards/backwards) uses two pointers from both ends. Much faster than creating reversed string and comparing!
Dating apps use two pointers to match users with compatible preferences in sorted lists. Efficient matching without checking all pairs!
The "Container With Most Water" problem models real scenarios like calculating water storage capacity between barriers, solved efficiently with two pointers.
Removing duplicates from sorted data (like logs or transactions) uses two pointers - one reads, one writes, processing in a single pass O(n) instead of O(n²).
Each pointer visits each element at most once, resulting in O(n) total operations
Reduces O(n²) nested loop solutions to O(n) - a massive improvement!
Sorting enables intelligent pointer movement, eliminating large portions of search space
Works for pairs, palindromes, sliding windows, and many other problems