How Do Inward Pointers Move? Ends, Palindromes, and Pair Sums
Inward pointers start at the two ends of an array and move toward the middle. A rule decides which end moves, and each step drops one index.
Inward pointers are two indexes. One starts at the first element and one at the last. A rule moves exactly one of them, or both when the ends match. They stop when they meet.
How it works
A palindrome compares the ends. Equal values mean both indexes move inward. A mismatch means the array is not a palindrome. An empty array and a one-element array never find a mismatch, so they count as palindromes.
A sorted pair sum compares the total of the ends. Too small means the left value cannot be part of a pair with anything still to its right that is even smaller, so you move the left pointer. Too large means you move the right pointer. The sorted order is what makes that discard safe. Unsorted data can hide the pair you just stepped over.
Each step retires one index, so the walk is O(n). You return indexes in ascending order, or [-1, -1] when the pointers cross.
Press Run to execute this example. Use console.log to print a value.
Expected output: [1, 3], then [-1, -1]. For target 10, the first total is 9, so the left pointer moves; 3 + 8 is 11, so the right pointer moves; 3 + 6 then matches.
Why it is correct
Suppose the current sum is too small. Pairing the current left value with any index left of right cannot produce a larger sum, so that left index cannot belong to a solution still under consideration. Moving left discards only impossible pairs. If the sum is too large, the symmetric argument makes right safe to discard. A returned pair was checked directly, and crossing pointers means every legal pair has been ruled out.
Cost
Each iteration moves at least one pointer inward, and neither pointer moves backward. There are at most n - 1 moves, so time is O(n) and extra space is O(1). This is better than checking all O(n²) pairs, but only because the input is sorted.
In the course
Sorted squares move the end whose square is larger. The next lesson uses the same inward shape for a palindrome and for the indexes of a pair. The earlier pair-sum exercise on the sorted-squares page only asks for a boolean. The follow-up asks for the indexes. That same lesson also compacts a sorted array with a write pointer, returning a new array of the unique values, and then measures the container between two line heights. Move the shorter height inward: the width shrinks, so that shorter line cannot form a larger area with any index still between the pointers. When the heights are equal, move the left index.
Common mistakes
Moving both pointers when the sum is only too small skips a pair that would have worked one step later.
Letting the indexes meet and using that single element twice. A pair needs two positions.
Applying the sum rule before the array is sorted. Sort first, or use a hash map instead.
When to use it
Use inward pointers when the ends of a sorted array, or the ends of a sequence you can compare directly, decide the next move.
When not to
Do not use them to find a pair in an unsorted array of arbitrary numbers. The discard step is only valid when order tells you which side is useless.
Problem-solving checklist
Name the fact that makes a discard safe; here it is ascending order. Decide whether pointers may meet. Trace which candidate pairs disappear after each move. Test a match at the ends, a match inside, no match, and fewer than two values.
Optional enrichment
Return every unique value pair that reaches the target in a sorted array with duplicates. After a match, skip repeated values on both sides and explain why that cannot discard a new value pair.