The two pointers technique uses two index variables that move through a data structure — usually an array or linked list — to solve problems in O(n) time that would naively require O(n²). It is one of the most frequently tested patterns in technical interviews and appears in problems ranging from pair sums to cycle detection.
Understanding two pointers unlocks a family of problems: sorted-array searches, palindrome checks, linked list cycles, and container problems all fall under this umbrella.
Quick reference
| Pattern | Data structure | Direction | Typical use |
|---|---|---|---|
| Opposite ends | Sorted array | → ← | Pair sum, palindrome, container water |
| Fast & slow | Linked list / array | → → (different speeds) | Cycle detection, middle of list, duplicate removal |
| Sliding window | Array / string | → → (fixed or variable window) | Substring problems, max subarray |
| Partition | Array | → ← or → → | QuickSort, 3-sum, Dutch flag |
Why two pointers work
Many array problems require comparing or combining elements at two positions. A brute-force approach tries every pair — O(n²). Two pointers exploit structure (sorted order, fixed-size window, or a monotonic property) to move intelligently, processing each element at most once — O(n).
Key insight: whenever you can decide which pointer to advance based on a comparison or condition, two pointers apply.
Pattern 1 — Opposite ends (sorted array)
Start one pointer at left = 0 and one at right = len - 1. Move them toward each other.
When to use:
- Array is sorted (or can be sorted without breaking the problem)
- You want a pair, triplet, or partition
Two Sum II (sorted array)
# LeetCode 167 — O(n) time, O(1) space
def two_sum(numbers: list[int], target: int) -> list[int]:
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
// JavaScript
function twoSum(numbers, target) {
let left = 0, right = numbers.length - 1;
while (left < right) {
const s = numbers[left] + numbers[right];
if (s === target) return [left + 1, right + 1];
else if (s < target) left++;
else right--;
}
return [];
}
// Java
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return new int[]{left + 1, right + 1};
else if (sum < target) left++;
else right--;
}
return new int[]{};
}
// Go
func twoSum(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
for left < right {
s := numbers[left] + numbers[right]
switch {
case s == target:
return []int{left + 1, right + 1}
case s < target:
left++
default:
right--
}
}
return nil
}
Pattern 2 — Valid palindrome
Check if a string is a palindrome by comparing characters from both ends:
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
LeetCode 125 variant (ignore non-alphanumeric):
def is_palindrome_125(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Pattern 3 — Container with most water
Heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
left right
Area = min(height[left], height[right]) * (right - left)
Move the shorter side inward to possibly find a taller boundary.
# LeetCode 11 — O(n) time, O(1) space
def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
best = max(best, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
Why move the shorter side? Moving the taller side can only decrease width while not gaining height — the area cannot increase.
Pattern 4 — Fast & slow pointers (Floyd's algorithm)
Two pointers advance at different speeds (fast moves 2 steps, slow moves 1). Used on linked lists and arrays.
Detect cycle in a linked list
# LeetCode 141 — O(n) time, O(1) space
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
Intuition: if there is a cycle, fast eventually laps slow inside the cycle. If no cycle, fast reaches None.
Find cycle start (Floyd's Part 2)
# LeetCode 142
def detect_cycle(head: ListNode | None) -> ListNode | None:
slow = fast = head
# Phase 1: find meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find cycle start
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
Middle of a linked list
# LeetCode 876 — O(n) time, O(1) space
def middle_node(head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second middle
Pattern 5 — Remove duplicates in-place
Use a write pointer (slow) and a read pointer (fast):
# LeetCode 26 — O(n) time, O(1) space
def remove_duplicates(nums: list[int]) -> int:
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[read - 1]:
nums[write] = nums[read]
write += 1
return write
function removeDuplicates(nums) {
if (!nums.length) return 0;
let write = 1;
for (let read = 1; read < nums.length; read++) {
if (nums[read] !== nums[read - 1]) {
nums[write++] = nums[read];
}
}
return write;
}
Pattern 6 — 3Sum
Reduce to 2Sum with two pointers for the inner loop:
# LeetCode 15 — O(n²) time, O(1) extra space
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate pivot
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return result
Pattern 7 — Trapping rain water
# LeetCode 42 — O(n) time, O(1) space
def trap(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
Key insight: water at position i is determined by min(left_max, right_max) - height[i]. The pointer on the shorter side always has a definite bound, so we can fill its water immediately.
Pattern 8 — Sort colors (Dutch National Flag)
Three-way partition with three pointers:
# LeetCode 75 — O(n) time, O(1) space
def sort_colors(nums: list[int]) -> None:
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# Note: do NOT increment mid after swapping with high —
# the swapped element needs to be examined.
Classic interview problems summary
| Problem | Pattern | LeetCode | Time | Space |
|---|---|---|---|---|
| Two Sum II (sorted) | Opposite ends | 167 | O(n) | O(1) |
| Valid Palindrome | Opposite ends | 125 | O(n) | O(1) |
| Container With Most Water | Opposite ends | 11 | O(n) | O(1) |
| Trapping Rain Water | Opposite ends | 42 | O(n) | O(1) |
| 3Sum | Opposite ends + sort | 15 | O(n²) | O(1) |
| Remove Duplicates | Fast/slow (write ptr) | 26 | O(n) | O(1) |
| Linked List Cycle | Fast/slow | 141 | O(n) | O(1) |
| Linked List Cycle II | Fast/slow | 142 | O(n) | O(1) |
| Middle of Linked List | Fast/slow | 876 | O(n) | O(1) |
| Sort Colors | Three pointers | 75 | O(n) | O(1) |
Two pointers vs sliding window
| Aspect | Two pointers | Sliding window |
|---|---|---|
| Primary use | Pair/triplet search, palindrome, partition | Contiguous subarray/substring |
| Direction | Opposite ends OR same direction | Same direction (window expands/shrinks) |
| Array required sorted? | Often yes (opposite ends) | No |
| Typical complexity | O(n) or O(n²) with sort | O(n) |
| Window size | Not a window — two independent positions | Fixed or variable window |
| Classic problems | Two Sum II, 3Sum, Container, Palindrome | Longest substring without repeat, Min window substring |
Rule of thumb: if you need a pair/triplet with a target sum in a sorted array, use two pointers (opposite ends). If you need a contiguous subarray satisfying a condition, use sliding window.
Complexity summary
| Pattern | Time | Space | Notes |
|---|---|---|---|
| Opposite ends (sorted) | O(n) | O(1) | Replaces O(n²) brute force |
| Fast/slow on linked list | O(n) | O(1) | Floyd's cycle detection |
| Write/read pointer | O(n) | O(1) | In-place modification |
| 3Sum (sort + two ptr) | O(n²) | O(1) | Sort is O(n log n) |
| Dutch flag (3 pointers) | O(n) | O(1) | One pass |
When to use two pointers
Use two pointers when:
- The array is sorted (or sorting it doesn't break constraints)
- You need pairs or triplets summing to a target
- You need to check or build a palindrome
- You need in-place duplicate removal or partition
- You are working with a linked list and need O(1) space for cycle detection or middle finding
- A brute-force O(n²) nested loop comes to mind and the array has order
Do NOT use two pointers when:
- The array is unsorted and you cannot sort it
- You need non-contiguous elements without a sum/comparison relationship
- The problem requires O(n) extra memory anyway (use a hash map instead)
- Order of traversal is not linear
Decision guide
Is data sorted or sortable?
├── Yes → Can problem be framed as: find pair/triplet with property?
│ ├── Yes → Two pointers (opposite ends)
│ └── No → Could be sliding window or binary search
└── No → Linked list with cycle or middle?
├── Yes → Fast/slow pointers
└── No → In-place partition/dedup?
├── Yes → Write/read pointer
└── No → Two pointers may not apply
Two pointers vs related techniques
| Technique | When | Key difference |
|---|---|---|
| Two pointers | Pair/triplet search, palindrome, partition | Two independent indices |
| Sliding window | Subarray/substring with condition | Contiguous window, expand+shrink |
| Binary search | Sorted array, find position | Halves search space each step |
| Hash map | Unsorted pair sum, frequency counts | O(n) space trade-off |
| Prefix sum | Range sum queries, subarray sum | Precompute cumulative sums |
Common mistakes
| Mistake | Fix |
|---|---|
| Moving both pointers unconditionally | Only move one pointer per iteration based on comparison |
Forgetting left < right guard |
Check guard in while condition and inner skip loops |
| Not skipping duplicates in 3Sum | After finding a triplet, advance past all duplicate left and right values |
| Using two pointers on unsorted data for sum problems | Sort first, or use a hash map |
Off-by-one in Dutch flag — incrementing mid after swapping with high |
Do NOT increment mid after swap with high; the swapped value needs inspection |
| Using fast/slow on singly-linked list without null checks | Always guard while fast and fast.next |
| Returning first middle for even-length list when second is wanted | Return slow (it lands on second middle after fast exhausts) |
| Treating opposite-ends and fast/slow as the same pattern | They are different sub-patterns with different invariants |
FAQ
Q: Do two pointers always require a sorted array?
A: No. Opposite-end two pointers for pair sums need sorted input. Fast/slow pointers and write/read pointers work on unsorted data.
Q: What is the difference between two pointers and a sliding window?
A: Two pointers track two independent positions (not necessarily adjacent). Sliding window maintains a contiguous range and grows/shrinks it. Sliding window is a specialisation of the same-direction two-pointer idea, but with the constraint that the window is contiguous.
Q: Can two pointers reduce O(n²) to O(n)?
A: Yes, when the data has monotonic structure that lets you decide which pointer to advance. For example, sorted arrays guarantee that a wrong comparison eliminates an entire half of the search space at each step.
Q: How do I recognise a two-pointer problem in an interview?
A: Look for: sorted array + target sum, palindrome check, linked list with O(1) space requirement, or in-place array transformation. If a brute-force nested loop naturally comes to mind, ask whether the array has order that lets you skip pairs.
Q: Why does Floyd's cycle detection work?
A: If a cycle exists, fast laps slow inside the cycle. The distance fast travels is always twice slow's. In Phase 2, after resetting slow to head, both pointers travel the same number of steps to reach the cycle entry — provable by modular arithmetic on the cycle length.
Q: Is two pointers the same as binary search?
A: No. Binary search halves the search space each step (O(log n)). Two pointers advance linearly but skip unnecessary comparisons using the array's structure. They both exploit sorted order differently.