Two Pointers
DSA · Arrays and Searching
Theory
The two-pointer technique uses two indexes that move through the data, either towards each other from both ends or in the same direction at different speeds. Each step uses a simple rule to decide which pointer to move, so the whole array is processed in a single pass. It often replaces a nested loop, reducing O(n²) to O(n).
Why we use it
It solves many pair, partition and in-place problems in linear time with constant extra memory.
When to use it
Use it on sorted arrays (pair sums), for reversing or partitioning in place, for removing duplicates, palindrome checks, and merging two sorted lists.
How it works
- Start: left = 0, right = n - 1 (sorted array)
- Is left < right? Yes: sum = arr[left] + arr[right]. No: Stop: no pair found.
- sum == target? Yes: Return the pair. No: Move one pointer.
- sum < target? Yes: left = left + 1 (need bigger). No: right = right - 1 (need smaller).
- Repeat
Syntax
left, right = 0, n-1
while left < right:
if condition met: record answer
elif need bigger: left += 1
else: right -= 1
Time: O(n) Space: O(1)Example
def pair_with_sum(sorted_nums, target):
left, right = 0, len(sorted_nums) - 1
while left < right:
total = sorted_nums[left] + sorted_nums[right]
if total == target:
return sorted_nums[left], sorted_nums[right]
if total < target:
left += 1
else:
right -= 1
return None
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
print(pair_with_sum([1, 3, 4, 6, 8, 11], 14))
print(is_palindrome("racecar"), is_palindrome("python"))Key points
- Usually needs sorted data or a clear moving rule
- Replaces nested loops with one pass
- Constant extra space
- Common in interview questions