Opposite-Direction Pointers

Foundations

Two pointers means two index variables moving through one array. In Arrays & Strings they were same-direction pointers: read and write both started at index 0 and moved right, suited to filtering in place. Opposite-direction pointers start at the two ends, left = 0 and right = n - 1, and step toward each other while left < right. They suit questions about pairs taken from both ends.

On nums = [7, 1, 5, 3, 6], left starts at index 0 and right at index 4. Stepping both inward visits mirrored pairs, nums[0] with nums[4] and then nums[1] with nums[3]: in general, index i meets index n - 1 - i. Every step moves at least one pointer inward, so the gap right - left shrinks by at least 1, and the walk ends within n - 1 steps: O(n) time and O(1) space.

Reversing nums in place puts the walk to work: swap nums[left] with nums[right], then step both inward. The 7 trades places with the 6, the 1 with the 3, and the pointers meet at index 2, leaving [6, 3, 5, 1, 7] with no second array. Other tasks keep the same walk and change only the rule for which pointer moves. That rule is the whole design.

• In-Place Read & Write Pointers

  That lesson moves read and write in the same direction through one array. This one starts two pointers at opposite ends.

  Open lesson

Case Scenario

Valid Palindrome runs that inward walk on a string, which is an array of characters indexed from 0: s[left] and s[right] are the mirrored pair, and a character that is not a letter or digit is skipped by moving only its own pointer. In s = "Top spot!", right steps past "!" first; then "T" at index 0 pairs with "t" at index 7, "o" with "o", and "p" with "p", ignoring case.

The obvious answer builds a cleaned copy, "topspot", and compares it with its reverse, shown below. It is correct and O(n) time, but it allocates two new sequences as long as the input before comparing a single pair: O(n) extra memory, which matters when s is a multi-megabyte document. Nothing in the question needs a copy, because every pair to compare already sits in s, at opposite ends.