Two Pointers
Two pointers, walking inward
The simplest version of the pattern, and the habit of naming what is already settled.
Key idea
The shape
One pointer starts at the left end, one at the right, and they move toward each other until they meet. Each pass compares the two ends and decides what to do next.
Because the pointers only ever move inward, the whole thing is one linear pass no matter how the moves are distributed. Every step retires at least one position, and there are only n positions.
Why it works
Say what is settled
The useful sentence for this loop is: everything strictly outside the range from left to right has already been checked and matched.
In the function above that sentence is not just a comment, it is the return value. What comes back is exactly the part that has not been settled yet.
That sentence is also why the loop can stop when the pointers meet. If everything outside is verified and nothing is left inside, there is nothing else to check. Getting into the habit of stating this now matters, because in the harder problems the sentence is the only thing standing between you and a guess.
Gotcha
`left < right`, not `left <= right`
Change that condition to left <= right and the loop runs one extra time when both pointers land on the same character, comparing it against itself. It matches, of course, so left moves past right and the slice comes back empty. The middle character silently disappears from the answer.
Whenever the body of the loop does something other than compare, such as counting a pair, swapping, or accumulating, that extra pass is a real bug rather than a wasted comparison.
Pick the condition from the invariant rather than by trial. If the range is meant to hold positions still to be settled, then left == right means one unsettled position, and whether you look at it depends on whether a single element can decide anything on its own.
Skipping positions you do not care about
A common variation is that only some positions count. Rather than building a cleaned copy of the input, advance each pointer past the characters that do not matter and work with what is left.
This keeps the extra space at O(1), which is usually the reason the problem is being asked in the first place. Below, only letters move; everything else stays exactly where it started.
Gotcha
The inner loops need the bound too
Both skip loops repeat left < right in their own condition. Without it, an input with no letters at all walks left straight past the end and the next index lookup raises IndexError.
Whenever an inner loop advances a pointer, it needs its own bound check. Relying on the outer condition is a bug that only shows up on inputs where everything gets skipped, which is exactly the input nobody tries by hand.
Tip
Normalize at the comparison, not in a copy
When the comparison itself is meant to ignore something, such as case, do that work where the two characters meet rather than by building a cleaned-up copy of the input first.
Lowercasing the whole string up front is easier to read and costs O(n) space, which throws away the only reason to be walking pointers instead of slicing. Comparing a.lower() against b.lower() at the point of comparison keeps the space constant.
Cost
Why this is still linear
The nested while loops look like they could make this quadratic, and they cannot. Each iteration of any loop here moves left right or right left, and the two pointers can move a combined total of n times before meeting.
This is the same total-work argument from the run-head guard in Unit 1: bound the work across the whole loop rather than per iteration. You will use it again for sliding windows and for monotonic stacks.
Predict the output: a missing bound
The inner skip loop has no bound of its own. Type what this prints, including the exception name if it raises one.
Converging pointer drills
Three functions on the same skeleton. pair_sums_from_ends pairs the outermost values, then the next pair inward, and so on. count_matching_ends counts how many pairs of characters match while walking inward, stopping at the first mismatch. has_pair_summing_to takes a sorted list and reports whether any two values add to the target.
Tests
print(pair_sums_from_ends([1, 2, 3, 4]), pair_sums_from_ends([1, 2, 3]), pair_sums_from_ends([5]))
print(count_matching_ends("abcba"), count_matching_ends("abcda"), count_matching_ends("xy"))
print(has_pair_summing_to([1, 3, 5, 8], 11), has_pair_summing_to([1, 3, 5, 8], 12))Output
Run the tests when you are ready.
Valid Palindrome
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.