Opposite-End Convergence

Concepts covered: Two-Pointer, Conditional Loops

Why 1 comparison retires many pairs

Take the 6 sorted amounts [1, 2, 4, 7, 9, 11] with a target of 11. Those values form 15 distinct pairs, and a nested loop visits all 15. Start a pointer at each end. The pair 1 and 11 sums to 12, over the target. Every other partner for 11 is at least as large as 1, so no pair holding 11 can reach the target: 1 comparison has retired 5 pairs. The right pointer steps to 9. Now 1 and 9 sum to 10, under the target. Every remaining partner for 1 is at most 9, so no pair holding 1 can work, and 4 more pairs are gone. The left pointer steps to 2, and 2 plus 9 is 11.

• Too large: retire 11 and the 5 pairs it belongs to
• Too small: retire 1 and its 4 remaining pairs
• Match at indexes 1 and 4, and the other 5 pairs are never checked

That's the argument the interviewer waits for, and it fits in 1 sentence: because the list is sorted, each comparison retires 1 element together with every pair that element belongs to, so the loop runs at most n times. Watch the 3 comparisons run over the same 6 amounts. The pointer that moves is always the one whose value caused the sum to miss, and the run stops the moment total == target.

nums = [1, 2, 4, 7, 9, 11]
target = 11
left, right = 0, len(nums) - 1
while left < right:
    total = nums[left] + nums[right]
    if total == target:
        print("pair at", left, right)
        break
    if total < target:
        left += 1
    else:
        right -= 1

pair at 1 4

The function to write from memory

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1    # too small: the left value cannot be in any answer
        else:
            right -= 1   # too large: the right value cannot be in any answer
    return []            # pointers met: every pair has been retired

Each iteration has exactly 3 outcomes: the pair matches and the function returns, the sum falls short and left moves right, or the sum runs long and right moves left. The loop ends when the pointers meet, and by then either a pair came back or every pair was retired. The animation prints pair at 1 4, the indexes rather than the values, because the question almost always wants positions, and a candidate who returns [2, 9] gets corrected and loses a minute.

The invariant, in 1 sentence

An invariant is a fact that holds before and after every iteration, and the one here is: if a matching pair exists, both of its elements sit between left and right inclusive. When the sum falls short, nums[left] paired with the largest value still in range was short, so it can't be half of any answer, and leaving it behind loses nothing. A sum that runs long retires nums[right] by the mirror argument. Once the pointers cross, the range is empty and no pair exists, which is why returning [] there is a proof rather than a guess.

Palindrome, the same walk on a string

The palindrome check is the phone-screen version of the same convergence. Pointers start at both ends of the string, the characters under them are compared, and both step inward on a match. A mismatch ends the function with False, and pointers that meet without a mismatch mean True. The cleaning line matters: "A man, a plan, a canal: Panama" is expected to pass, so lowercase the text and keep only letters and digits before the loop, and say that you are doing it.

def is_palindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Reverse and compare: s == s[::-1]

• 1 line, and it's correct
• Allocates a second string of n characters
• Shows that you know a slice, which the interviewer assumed
• Leaves the convergence pattern undemonstrated

Converging pointers

• 9 lines, and it is correct
• Allocates 2 integers after the cleaning step
• Shows the loop the question was written to test
• Stops at the first mismatch rather than reversing the whole string

Write the pointer version first, then mention the slice as the 1-line Python shortcut. The interviewer asked a palindrome question to see the convergence loop; showing the slice and stopping reads as not knowing the pattern, and showing it second reads as knowing both. Both run in O(n) time. The difference is space, and the follow-up asks which one uses extra memory even on a 10-character string where nobody could measure it. The slice builds a reversed copy; the pointers hold 2 positions. The cleaning step also builds a new string, so the accurate claim is "O(1) extra beyond the cleaned copy", and that qualifier, offered unprompted, says you count allocations rather than recite them.

About this lesson

This section is part of the Two Pointers: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.