Foundation · Module 6 · Lesson 1
Opposite-direction pointers
Narrow a sorted search space from both ends.
Lesson 32 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Step-through visualizer
Two Pointers
Follow the state transition, then use the controls to test your prediction.
Opposite-Direction Pointers: Shrinking the Search Space
The opposite-direction two-pointer technique initializes one pointer at the start (left = 0) and one at the end (right = n - 1) of a sorted array or linear structure. At each iteration, comparing the elements allows you to eliminate an entire row or column of candidate pairs in O(1) time rather than evaluating all O(n²) combinations.
Architectural Boundary · Do Not Confuse
Brute Force: O(n²)
Opposite Pointers: O(n)
Brute force checks every (i, j) pair. Opposite pointers use the monotonic sorting invariant: if sum < target, left++ is the only move that can increase the sum; right-- would only decrease it.
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};
if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}Active Recall Checkpoint
Why does opposite-direction pointer traversal strictly require the array to be sorted?
Show answer & explanation
Without monotonic ordering, incrementing left or decrementing right has unpredictable effects on sum or boundary constraints, making it impossible to discard half of the search space with certainty.
Use it when
Use opposite pointers for sorted arrays, palindrome verifications, container with most water, and 3Sum reductions.
Reconsider when
Reconsider when elements are unsorted and sorting (O(n log n)) exceeds the time budget of a frequency hash map (O(n)).
Cost Model
Complexity & Trade-offs
Hands-On Practice
Implement: Two Sum II (Opposite Pointers)
Write and test your solution in the browser against automated verification test cases.
Two Sum II (Opposite Pointers)
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices [index1, index2] (1-indexed).
When to use it
- Sorted pair search, compaction, merging, partitioning, and palindrome checks.
- Replacing nested loops when boundaries move monotonically.
- Maintaining disjoint processed and candidate regions.
Common mistakes
- Moving a pointer without proving the discarded region is impossible.
- Forgetting duplicate skipping in enumeration problems.
- Applying an order-dependent pointer rule to unsorted data.
Practice prompts
- Reproduce the worked Opposite-direction pointers example without looking at the trace.
- Change one input condition and explain whether the Opposite-direction pointers invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check