Two pointers: definition
Track two positions in an array or string and move them according to a rule. The pointers can move toward each other or in the same direction, often avoiding a nested loop.
Problems this pattern can solve
- Pair sum in a sorted array
- Check whether a string is a palindrome
- Remove duplicates from a sorted array in place
- Merge two sorted arrays
Task example: pair sum
Given an ascending sorted integer array and a target, return True if two values at different indices add up to the target. Otherwise, return False.
Duplicates and negative numbers are allowed. You cannot reuse one element. Fewer than two elements means False.
nums = [1, 2, 4, 6, 7], target = 9
True: 2 + 7 = 9
Two-pointer video example
nums = [1, 2, 4, 6, 9], target = 8
True: 2 + 6 = 8
Brute force: video explanation
nums = [1, 2, 4, 6, 7] · target = 9
Prefer reading? Follow the steps below.
- Pick the first number and add it to each number after it. This checks every pair without using the same element twice.
- If no pair matches, move to the next number and repeat. Return True as soon as a pair adds up to the target; return False if every pair fails.
- In this example, 1 pairs with 2, 4, 6, and 7 without reaching 9. Next, 2 pairs with 4, 6, and finally 7: 2 + 7 = 9, so stop and return True.
Time complexity · O(n²)
With n numbers, there are n(n − 1)/2 possible pairs. Checking all of them takes O(n²) time in the worst case.
Space complexity · O(1)
Only loop indices are stored. No extra array is created.
Two pointers: video explanation
nums = [1, 2, 4, 6, 9] · target = 8
Prefer reading? Follow the steps below.
- Place left at the smallest number and right at the largest. Add the two values.
- If the sum is too large, move right one place left to try a smaller number. If it is too small, move left one place right to try a larger number.
- Return True when the sum matches. If the pointers meet without a match, return False: no pair remains.
- In this example, 1 + 9 = 10 is too large, so move right to 6. Now 1 + 6 = 7 is too small, so move left to 2. Then 2 + 6 = 8: return True.
Why it works: sorted order lets us rule out one number at each step. When the sum is too small, the left number cannot work with any remaining partner. When it is too large, the right number cannot work with any remaining partner.
Use an array sorted in ascending order for two pointers.
Time complexity · O(n)
Each step moves one pointer inward. There are at most n − 1 comparisons, so the worst-case time grows linearly with the array size.
Space complexity · O(1)
Only two indices and the current sum are stored. No extra array is needed.
Compared with brute force, two pointers skips pairs that cannot work. For sorted input, it improves worst-case time from O(n²) to O(n), while keeping extra space at O(1).