Two Pointers Technique: Efficient Array Traversal
Master the two pointers technique for O(1) space complexity solutions to array problems like pair sum, palindrome check, and triplet finding.
Two Pointers Technique: Efficient Array Traversal
The two pointers technique is a fundamental optimization pattern that transforms O(n²) or O(n³) brute-force solutions into elegant O(n) single-pass algorithms. Instead of nested loops that check every possible combination, two pointers work from opposite ends of a data structure—or move in lockstep—to find solutions with constant extra space.
This pattern shines when solving problems involving sorted arrays, pair sums, substring searches, and cycle detection. The core insight is simple: by positioning two pointers strategically and moving them based on comparison results, you can avoid the combinatorial explosion of brute-force approaches.
Introduction
The two pointers technique transforms O(n²) or O(n³) brute-force array traversal into elegant O(n) single-pass algorithms. By positioning two pointers strategically—either at opposite ends converging inward, or at the same end moving at different speeds—and moving them based on comparison results, you can avoid the combinatorial explosion of nested loops.
This matters because it delivers constant-space solutions (O(1)) for problems involving sorted arrays, pair sums, palindrome checks, and cycle detection. In technical interviews, two pointers consistently appear because it demonstrates you can optimize beyond naive approaches and think about data structure traversal intelligently. The pattern also extends to linked list problems and sliding window variants.
This guide covers both two-pointer patterns: opposite-ends for pair sums and palindromes, and slow/fast for cycle detection and in-place modifications. You’ll understand when two pointers apply versus hashing or sorting, see production failure scenarios like infinite loops and off-by-one errors, and work through interview questions with detailed explanations.
When to Use
The two pointers technique works best when:
- Sorted input is available or can be sorted — The ordering lets you make decisions about pointer movement
- You need O(1) space complexity — Unlike hash map solutions, two pointers use only a few variables
- Targeting pair, triplet, or k-sum problems — Classic problems like “two sum in sorted array” or “valid palindrome”
- Palindrome or substring validation — Left and right pointers comparing characters from opposite ends
When Not to Use
- Unsorted arrays where sorting first gives you O(n log n) overhead but may still be worthwhile
- Problems requiring all combinations rather than valid pairs
- Scenarios where hash map O(n) time with O(n) space is clearer and faster in practice
Architecture: How Two Pointers Works
graph LR
A["Start: Left=0, Right=n-1"] --> B{"Left < Right?"}
B -->|Yes| C[Compare elements]
C --> D{"Condition met?"}
D -->|Yes| E[Return result]
D -->|No| F{"What to move?"}
F --> G["Move Left++"]
F --> H["Move Right--"]
G --> B
H --> B
B -->|No| I[No solution found]The pointer movement strategy depends on whether you need to increase or decrease the current sum/value to reach your target.
Production Failure Scenarios
| Failure | Cause | Mitigation |
|---|---|---|
| Infinite loop | Pointer not moving in all code paths | Ensure both pointers move on every iteration |
| Missed solutions | Incorrect initial positions | Verify start/end positions match problem constraints |
| Off-by-one errors | Using <= vs < in termination condition | Test boundary cases (empty array, single element) |
| Wrong direction | Moving wrong pointer based on comparison | Clarify logic: should sum increase or decrease? |
Trade-off Table
| Approach | Time | Space | Use Case |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Small inputs, no extra space available |
| Hash Map | O(n) | O(n) | Unsorted input, need fast lookups |
| Two Pointers | O(n) | O(1) | Sorted input, pair/sum problems |
| Binary Search | O(log n) | O(1) | Searching single target in sorted array |
Implementation
Pair Sum in Sorted Array
def pair_sum_sorted(arr, target):
"""
Find pair with target sum using two pointers.
Returns indices of the pair, or (-1, -1) if none exists.
"""
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return [-1, -1]Palindrome Check
def is_palindrome(s):
"""
Check if string is palindrome using two pointers.
"""
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric characters
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 TrueRemove Duplicates from Sorted Array
def remove_duplicates(nums):
"""
Remove duplicates in-place and return new length.
Uses slow pointer pattern.
"""
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1Common Pitfalls / Anti-Patterns
- Forgetting to handle empty or single-element inputs — Always check edge cases first
- Not moving both pointers when needed — In some problems only one pointer moves per iteration
- Confusing “slow/fast” with “left/right” patterns — Slow/fast is for cycle detection, left/right for opposite-end traversal
- Mutable default arguments — Don’t use empty lists or dicts as default parameters
Quick Recap Checklist
- Input sorted? Two pointers may apply
- Need O(1) space? Two pointers good fit
- Pair/triplet sum problem? Consider two pointers first
- Both pointers moving? Ensure no infinite loop
- Test boundary: empty array, one element, all same values
Interview Questions
Brute force checks every pair with nested loops — O(n²). Two pointers make a single pass, each moving at most n positions, so it's O(n). Because the array is sorted, you make intelligent decisions: if the sum is too small, move the left pointer right; if too large, move the right pointer left.
Opposite ends puts one pointer at the start and one at the end, moving them toward each other. Works for pair sums, palindrome checks, sorted array problems.
Slow/fast puts both pointers at the start. The fast pointer races ahead while the slow pointer marks a position. Good for removing duplicates, partitioning arrays, and cycle detection.
Yes — use the slow/fast pattern for cycle detection. Put both at head, move fast 2x speed. If they meet, a cycle exists. To find the cycle start, take the meeting point, reset one pointer to head, then move both 1x speed until they meet again at the cycle origin.
Every element outside the current pointer window has already been ruled out as part of a valid solution. If arr[left] + arr[right] > target and the array is sorted ascending, any element between left and right would only increase the sum — so moving right inward is safe.
Fix one pointer at index i, then run the standard pair-sum two-pointer technique on the remaining window (i+1 to n-1). This cuts brute force from O(n³) to O(n²) with O(1) space.
- Sort the array first
- For each i, set left=i+1, right=n-1, target=-arr[i]
- Move pointers as in pair-sum; skip duplicates to avoid repeated triplets
- Complexity: O(n²) time, O(1) extra space
The opposite-ends pattern requires sorted input because pointer movement decisions depend on the ordering. If the input is unsorted, you have options:
- Sort first (adds O(n log n)) then apply two pointers
- Use a hash map instead (O(n) time, O(n) space)
- Use the slow/fast pattern for in-place operations like partition or deduplication, which does not need sorted input
The slow/fast pattern does this cleanly: move slow one step and fast two steps per iteration. When fast reaches the end, slow lands on the middle. Even-length lists produce the first middle element by default, though the behavior depends on your loop termination condition.
- Initialize slow = fast = head
- While fast and fast.next are not null: slow = slow.next, fast = fast.next.next
- Return slow
Both give O(n) time, but the costs differ. Two pointers need O(1) space but require sorted input (or O(n log n) to sort first). Hash maps work on unsorted input directly but consume O(n) space. Pick two pointers when memory is tight; pick the hash map when the input is already unsorted and you want a simpler implementation.
After finding a valid pair, skip over duplicates by advancing both pointers past repeated elements before continuing:
- When arr[left] + arr[right] == target, record the pair
- Increment left while arr[left] equals the previous value
- Decrement right while arr[right] equals the next value
- This way each distinct pair appears exactly once in the output
You have vertical lines at each index and want the pair that holds the most water. Area equals width times the shorter of the two heights. Start pointers at opposite ends, compute the area, then move the pointer at the shorter height inward. The reasoning: keeping the shorter line and moving the taller one can only decrease the area.
- Initialize left=0, right=n-1, max_area=0
- While left < right: compute area, update max, move the pointer with smaller height
- If heights are equal, moving either works
- Time: O(n), Space: O(1)
Water at any position depends on the maximum height to its left and right. Take the lower of those two maxima and subtract the bar height at that position — that's how much water sits there. Two pointers track those maxima from opposite ends, moving the pointer with the smaller max inward each step.
- Track left_max and right_max as you move inward
- If the current bar is shorter than the opposing max, water accumulates
- If the current bar is taller, it becomes the new max on that side
- Time: O(n), Space: O(1)
Find the middle with slow/fast pointers, reverse the second half in place, then compare nodes from both halves moving outward. If all pairs match, it's a palindrome.
- Find the middle node using two pointers
- Reverse the second half of the list
- Compare the start half with the reversed second half
- Restore the original list structure if your interviewer cares about side effects
Valid Palindrome II allows deleting at most one character to make a string read the same forwards and backwards. Two pointers move inward; when they find a mismatch, skip either the left character or the right one and check if the remaining substring is a palindrome. Only one skip is allowed, so track whether you've already skipped.
- Move left and right inward until a mismatch occurs
- On mismatch, test two possibilities: skip left char or skip right char
- Only one skip permitted — use a flag to enforce this
- Return true if either path produces a palindrome
Walk both arrays from the start simultaneously. If values match, add to the result and advance both pointers. If one value is smaller, advance that pointer. Continue until one array is exhausted.
- Initialize i=0, j=0 for both arrays
- If arr1[i] == arr2[j]: record intersection, advance both
- If arr1[i] < arr2[j]: advance i
- If arr1[i] > arr2[j]: advance j
- Time: O(n+m), Space: O(1) excluding output
The slow pointer marks where the next non-zero element goes. The fast pointer scans forward looking for non-zeros; when found, swap with the element at slow and increment slow.
- slow starts at 0; iterate fast from 0 to n-1
- When nums[fast] is non-zero, swap with nums[slow] and increment slow
- All elements before slow are non-zero; everything after is zeros
- Single pass, O(n) time, O(1) space
This is a sliding window problem at heart, but two-pointer logic applies directly. Expand the window with a right pointer, contract from the left when distinct count exceeds K, and count subarrays ending at each position.
- Maintain a window [left, right] and a frequency map
- Expand right to include new elements; contract from left when distinct count exceeds K
- Count valid subarrays using the current window size
- Time: O(n), Space: O(k) for the frequency map
Track a window that resets whenever you hit a zero (product becomes 0). Within the window, count negatives. An even count means the whole window works; an odd count means you exclude everything up to the most recent negative.
- Reset the window when a zero appears
- Track the last negative index and the running negative count
- Even negatives in window: the whole window is valid
- Odd negatives: valid window starts after the last negative
- Time: O(n), Space: O(1)
Opposite ends places pointers at both boundaries and moves them toward each other — good for pair sums and palindrome checks where the search space shrinks predictably. Sliding window keeps both pointers moving forward, with the left sometimes lagging behind, and the window size can grow and shrink based on a condition — better for substring and subarray problems.
- Opposite ends: left and right converge — useful for bounded search spaces
- Sliding window: both move forward; left can lag to shrink the window
- Sliding window handles variable-size windows; opposite ends targets fixed targets
- Both achieve O(n) time with O(1) space when applicable
The most common failures are off-by-one errors in the termination condition and pointers that don't move in every code path. Handle these explicitly:
- Check for empty or null input before the loop starts
- Handle single-element inputs before entering the main loop
- Use `while left < right` instead of `<=` — the latter revisits elements
- Make sure both pointers move on every iteration to avoid infinite loops
- Validate bounds before accessing array elements
4Sum fixes two elements instead of one, then runs two-pointer pair-sum on the remaining window. O(n³) instead of O(n⁴) brute force, with O(1) extra space.
- Sort the array first
- Fix the first element with a loop, then the second with an inner loop
- Set left=j+1, right=n-1 and solve the pair-sum subproblem
- Skip duplicates after each valid quadruplet
- Complexity: O(n³) time; prune branches where the sum cannot reach the target
Further Reading
- LeetCode Two Pointers Guide — Curated problems ranked by difficulty
- GeeksforGeeks: Two Pointers Technique — Comprehensive tutorial with visual walkthroughs
- Visualgo: Sorting & Two Pointers — Interactive algorithm visualization
- Cracking the Coding Interview — “The Two Pointer Approach” chapter, pages 90-96
- Clean Code Handbook — Real-world interview strategies for pointer-based problems
Conclusion
Two pointers turn O(n²) pair finding into a single O(n) scan on sorted input. The move is simple: position pointers at opposite ends for pair sums, or use slow/fast for deduping and cycle detection, then advance based on what you see. The gotchas are pointer placement and termination conditions—those trip people up in interviews. For more traversal patterns, see Binary Search Variants or Depth-Limited Search.
Category
Related Posts
Sliding Window: Dynamic Subarray Problems
Solve maximum subarray, longest substring, and subarray average problems with O(n) time using the sliding window technique.
Arrays vs Linked Lists: Understanding the Trade-offs
Compare arrays and linked lists in terms of access time, insertion/deletion efficiency, memory usage, and cache performance.
Arrays: 1D, 2D, and Multi-dimensional Mastery
Master array operations, traversal, search, common patterns like two-pointer and sliding window, and when to use multi-dimensional arrays.