Pointers from both ends
In one line
Start one pointer at each end of a sorted array or string and move them toward each other, discarding a whole set of candidates with every step, so one O(n) pass replaces checking all pairs.
What it is
The opposite-ends technique keeps two indexes, lo at the start and hi at the end. At each step you compare the two elements and move one pointer (or both) inward, stopping when they meet.
It works when the situation at the two ends tells you which side can be safely dropped. In a sorted array, if a[lo] + a[hi] is too small, no partner for a[lo] can work except larger values, which are not there, so lo moves. In palindrome checks, the two ends must match, so both move. Each step removes at least one element from consideration, giving O(n) time and O(1) space.
Why interviewers ask
It is the standard way to turn an O(n^2) all-pairs search into O(n) without extra memory. Interviewers want the argument for why moving a pointer never skips the answer, not just the code. Questions like valid palindrome, two sum on a sorted array, container with most water and reversing in place all test it.
How it works
- 1Set lo = 0 and hi = n - 1. Loop while lo < hi.
- 2Look at the pair (a[lo], a[hi]) and record anything useful (a match, a best area so far).
- 3Decide which pointer to move with a rule that is provably safe: the element you drop cannot be part of any better answer with the remaining elements.
- 4Two sum in a sorted array: if the sum is too small, lo += 1 (a[lo] is too small even with the largest remaining value); if too large, hi -= 1.
- 5Container with most water: area = (hi - lo) * min(height[lo], height[hi]). Move the shorter line, because any container keeping it would be narrower and no taller.
- 6Each iteration moves at least one pointer, so the loop runs at most n - 1 times: O(n) time, O(1) extra space.
Worked example · Container with most water: height = [1, 5, 4, 3]
- lo = 0 (height 1), hi = 3 (height 3). Width 3, height min(1, 3) = 1, area 3. best = 3. Line 0 is shorter, so lo = 1.
- lo = 1 (height 5), hi = 3 (height 3). Width 2, height 3, area 6. best = 6. Line 3 is shorter, so hi = 2.
- lo = 1 (height 5), hi = 2 (height 4). Width 1, height 4, area 4. best stays 6. hi = 1.
- lo = hi, stop. Answer 6, from lines 1 and 3.
- Why moving the shorter line was safe at step 1: any container using line 0 has height at most 1 and width at most 3, so it can never beat 3. We checked 3 pairs instead of all 6.
Picture it
Two people searching a row of seats for a pair whose ticket numbers add up to a target: one starts at the cheapest seat, the other at the most expensive. If their total is too low, the cheap-end person steps up; if too high, the expensive-end person steps down. They never need to go back.
Reference code
def max_area(height):
lo, hi = 0, len(height) - 1
best = 0
while lo < hi:
width = hi - lo
best = max(best, width * min(height[lo], height[hi]))
if height[lo] < height[hi]: # the shorter line limits the area,
lo += 1 # so move it and hope for a taller one
else:
hi -= 1
return best
def is_palindrome(s):
lo, hi = 0, len(s) - 1
while lo < hi:
if not s[lo].isalnum():
lo += 1
elif not s[hi].isalnum():
hi -= 1
elif s[lo].lower() != s[hi].lower():
return False
else:
lo += 1
hi -= 1
return True
max_area records each container's area and moves the pointer at the shorter line, since that line caps every narrower container that keeps it. is_palindrome skips non-alphanumeric characters from either side and compares case-insensitively. Both run in O(n) time and O(1) space.
Key patterns
Sorted pair search
When: Find a pair with a target sum, closest sum, or count pairs below a target in a sorted array
How: Move lo up when the sum is too small, hi down when too large; for counting pairs with sum < target, add hi - lo when a[lo] + a[hi] < target, then lo += 1.
Symmetry check
When: Palindromes, valid palindrome after deleting one character
How: Compare ends and move both inward; on a mismatch, try skipping either side once.
Greedy shrink (move the limiting side)
When: Container with most water, boats to save people
How: The side that limits the answer is the one to move, because keeping it cannot improve the result.
In-place reverse
When: Reverse an array, string or a segment of one
How: Swap a[lo] and a[hi], then lo += 1 and hi -= 1 until they meet.
Real-world use
Reversing in standard libraries
C++ std::reverse and CPython's list.reverse swap the first and last elements and walk inward until the indexes meet, the simplest opposite-ends loop.
Quicksort partitioning
Hoare's partition scheme, the basis of the partition step in many quicksort and introsort implementations such as C++ std::sort, scans from both ends, swapping elements that are on the wrong side of the pivot until the scans cross.
Budget pairing in shopping features
A 'two items under your budget' or gift-bundle feature on a price-sorted catalog can find the pair closest to the budget with lo at the cheapest item and hi at the most expensive, in one pass instead of comparing every pair.
Text validation
Palindrome and symmetry checks in string utilities and coding platforms compare characters from both ends, skipping punctuation, and stop at the first mismatch.
In a project
A travel site wants to suggest an outbound and return flight pair whose combined price is as close as possible to the user's budget, from two price-sorted lists of about 5,000 flights each.
- Sort outbound prices ascending and return prices descending (or index the return list from the end).
- Put pointer i at the cheapest outbound and j at the most expensive return; compute the total and record it if it is closest to the budget so far.
- If the total is over budget, move j to a cheaper return; if under, move i to a pricier outbound; stop when either list runs out.
- Filter out pairs that fail other rules (return before outbound date) before the search, so the pointer logic stays simple.
Impact: The best pair is found in about 10,000 steps instead of 25 million pair comparisons, so suggestions appear instantly and the search can run for every user without a cache.
Trade-offs
Use it when
- The input is sorted, or symmetric structure matters (palindromes, reversal)
- You need O(1) extra space
- You can prove a rule for which end to discard at each step
Avoid it when
- The input is unsorted and you need original indexes: sorting costs O(n log n) and loses positions, so a hash map is often better
- There is no safe rule for which side to move
- You need all pairs, not one best pair; the output itself may be O(n^2)
Cost: O(n) time, O(1) extra space. Add O(n log n) if you must sort first.
Common mistakes
- Using lo <= hi when the two pointers must point at different elements, which pairs an element with itself.
- Applying the technique to an unsorted array for a sum problem, where moving a pointer is no longer safe.
- Moving the taller line in container with most water, which can skip the optimal pair.
- Not being able to explain why the moves are safe; interviewers usually ask.
- Forgetting to advance a pointer in some branch, causing an infinite loop.
Interview questions
Quick revision
- lo = 0, hi = n - 1, loop while lo < hi.
- Each step drops at least one candidate: O(n) time, O(1) space.
- Sorted sum: too small -> lo += 1; too big -> hi -= 1.
- Container: area = width * min(height); move the shorter line.
- Palindrome: compare ends, move both; skip junk characters.
- Unsorted input: sort first (O(n log n)) or use a hash map.
- Always be ready to prove why the pointer move is safe.
Check yourself
1. In a sorted array, a[lo] + a[hi] is less than the target. What should you do?
2. What is the time complexity of the opposite-ends two sum on a sorted array of n elements?
3. For height = [2, 1, 2], what is the maximum water container area?
4. Why does the opposite-ends technique usually need sorted input for sum problems?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.