Two pointers is a technique where we use two references (usually indices) to traverse an array or linked list. Instead of checking every possible pair with nested loops (O(n²)), we move the pointers strategically to get O(n) solutions.
In simple language, think of it like two fingers on a ruler. We move them based on some condition, and they narrow down the answer without checking every combination.
The Three Patterns
Almost every two pointer problem falls into one of these patterns:
Pattern 1: Opposite Direction
Two Sum (Sorted Array)
Given a sorted array and a target sum, find two numbers that add up to the target. We start with pointers at both ends. If the sum is too small, move the left pointer right (bigger number). If it’s too big, move the right pointer left (smaller number).
function twoSum(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) left++; // need bigger sum
else right--; // need smaller sum
}
return [-1, -1]; // no pair found
}
// twoSum([1, 3, 5, 7, 11], 12) => [1, 4] (3 + 11 = 14 -> too big,
// 3 + 7 = 10 -> too small, 5 + 7 = 12 -> found!)def two_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
total = arr[left] + arr[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need bigger sum
else:
right -= 1 # need smaller sum
return [-1, -1] # no pair found
# two_sum([1, 3, 5, 7, 11], 12) => [2, 3] (5 + 7)static int[] twoSum(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++; // need bigger sum
else right--; // need smaller sum
}
return new int[]{-1, -1}; // no pair found
}
// twoSum([1, 3, 5, 7, 11], 12) => [2, 3] (5 + 7)Time: O(n), Space: O(1). Compare that to the brute force O(n²) nested loop approach.
Reverse an Array
Classic opposite direction — swap elements at left and right, then move inward.
function reverseArray(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]; // swap
left++;
right--;
}
return arr;
}
// reverseArray([1, 2, 3, 4, 5]) => [5, 4, 3, 2, 1]def reverse_array(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left] # swap
left += 1
right -= 1
return arr
# reverse_array([1, 2, 3, 4, 5]) => [5, 4, 3, 2, 1]static void reverseArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right]; // swap
arr[right] = temp;
left++;
right--;
}
}
// reverseArray([1, 2, 3, 4, 5]) => [5, 4, 3, 2, 1]Time: O(n), Space: O(1). In-place reversal, no extra array needed.
Pattern 2: Same Direction
Remove Duplicates from Sorted Array
We need to modify the array in-place and return the count of unique elements. The slow pointer marks where the next unique element should go. The fast pointer scans ahead.
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let slow = 0; // position of last unique element
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast]; // write unique element
}
}
return slow + 1; // count of unique elements
}
// removeDuplicates([1,1,2,2,3]) => 3, array becomes [1,2,3,...]def remove_duplicates(nums):
if not nums:
return 0
slow = 0 # position of last unique element
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast] # write unique element
return slow + 1 # count of unique elements
# remove_duplicates([1,1,2,2,3]) => 3, list becomes [1,2,3,...]static int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0; // position of last unique element
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast]; // write unique element
}
}
return slow + 1; // count of unique elements
}
// removeDuplicates([1,1,2,2,3]) => 3, array becomes [1,2,3,...]Time: O(n), Space: O(1). The fast pointer reads, the slow pointer writes. Clean and efficient.
Pattern 3: Fast & Slow (Floyd’s Cycle Detection)
Detect a Cycle in a Linked List
The slow pointer moves 1 step at a time, the fast pointer moves 2 steps. If there’s a cycle, they’ll eventually meet. If there’s no cycle, the fast pointer hits the end.
Think of it like two runners on a track. If the track is circular, the faster runner will eventually lap the slower one.
function hasCycle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next; // 1 step
fast = fast.next.next; // 2 steps
if (slow === fast) return true; // they met -- cycle!
}
return false; // fast hit the end -- no cycle
}def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow == fast:
return True # they met -- cycle!
return False # fast hit the end -- no cyclestatic boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 1 step
fast = fast.next.next; // 2 steps
if (slow == fast) return true; // they met -- cycle!
}
return false; // fast hit the end -- no cycle
}Time: O(n), Space: O(1). Without this trick, we’d need a hash set to track visited nodes (O(n) space).
Find the Middle of a Linked List
Same idea but simpler. When the fast pointer reaches the end, the slow pointer is at the middle.
function findMiddle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow is at the middle
}def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at the middlestatic ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow is at the middle
}How to Recognize a Two Pointer Problem
Look for these clues:
- The array is sorted (or can be sorted) — opposite direction likely works
- We need to find a pair that satisfies some condition
- We need to do something in-place with O(1) space
- The problem involves a linked list (cycle, middle, intersection)
- The brute force involves nested loops comparing pairs — two pointers can often reduce it to a single pass
In simple language, whenever we see “sorted array” and “find a pair” in the same problem, our first thought should be two pointers from opposite ends. It’s one of those patterns that, once we see it, we can’t unsee it.