Two pointers

Sorting buys locality: closely related values end up near each other, so answers become local instead of requiring all-pairs checks.

The structure it imposes is simple to state. Small values sit left, big values sit right, and close values are adjacent.

This lesson exploits exactly that. With a sorted list, a pair-sum question needs one pass with two pointers rather than the O(n²) nested loop from lesson 1-1.

The extra benefit is memory. The hash-set solution to pair-sum was also O(n) time but needed O(n) space, and sortedness gives that space back.

Two pointers

A pointer here is just an index variable. The two-pointer pattern keeps two of them, usually lo at the start and hi at the end, and moves them toward each other based on what they see.

Take pair-sum on a sorted list, asking whether any pair adds to target.

• If nums[lo] + nums[hi] is too small, the only way to grow the sum is lo += 1. Everything left of hi paired with nums[lo] would be even smaller, so nums[lo] is dead and can be discarded.
• If it is too big, shrink with hi -= 1 for the mirror reason.
• Equal means the pair is found.

Every step permanently retires one element, and that is what bounds the work. There are n elements to retire, so the whole scan is O(n) time and O(1) space.

Compare lesson 1-1, where the set solution was O(n) time but O(n) space. Sortedness bought the memory back, at the cost of requiring a sort in the first place.

Pair-sum with converging pointers

The trace shows both pointers and the sum at each step.

def pair_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        print(f"lo={lo} hi={hi} sum={s}")
        if s == target:
            return nums[lo], nums[hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

print(pair_sum_sorted([1, 3, 4, 6, 8, 11], 14))

Output

lo=0 hi=5 sum=12
lo=1 hi=5 sum=14
(3, 11)

Two comparisons found 3 + 11 = 14 in a six-element list, and the nested loop would have checked several pairs to reach the same place.

The first step summed 1 + 11 = 12, short of 14, so lo advanced and the 1 left the search permanently. That single move is what the next block justifies.

The loop condition is lo < hi rather than lo <= hi, which matters here. Allowing them to be equal would let an element pair with itself, and the question asks about two distinct positions.

return None fires when the pointers meet without success, and at that point every element has been retired, so the absence is proved rather than assumed.

is_palindrome

A palindrome reads the same forwards and backwards, which is a two-pointer question.

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return False
        lo += 1
        hi -= 1
    return True

print(is_palindrome("racecar"))
print(is_palindrome("napkin"))
print(is_palindrome("abba"))

Output

True
False
True

The skeleton is pair_sum_sorted with a different test. Two pointers start at the ends, and the loop runs while lo < hi.

Here both pointers always move, since a matching pair retires two characters at once. That makes the loop run about n/2 times, which is still O(n).

Odd and even lengths both work without special cases. racecar leaves its middle e unchecked, which is correct since a single character always matches itself, and abba ends when the pointers cross between the two b's.

The early return False is the efficiency here. napkin fails on its very first comparison, so a long non-palindrome costs almost nothing.

The O(1) space is what makes this the preferred answer over s == s[::-1], which is shorter but builds a full reversed copy.

Because nums[hi] is the largest remaining partner, and even with it nums[lo] fell short, so nums[lo] cannot pair with anything.

The list is sorted, so every value still in play between lo and hi is at most nums[hi]. If nums[lo] + nums[hi] is already less than the target, then nums[lo] plus any other candidate is smaller still.

That makes retiring nums[lo] lossless. It is not a heuristic or a gamble, it is a proof that no answer involving that element exists.

This is the exchange-style argument that makes two pointers correct, and the same shape appears again in the greedy proofs of unit 8.

Being able to say it out loud is what interviewers grade. Writing the loop is easy, and justifying why discarding an element cannot lose the answer is the part that distinguishes understanding from memorization.

Same-direction pointers: reader and writer

Converging lo and hi pointers are half the pattern. The other half moves two pointers in the same direction at different speeds, usually named read and write.

The reason this variant exists is a constraint. Many problems demand editing a list in place, with O(1) extra space and no second list, and one index cannot both scan the input and mark where the cleaned-up output ends.

• read visits every element.
• write marks the boundary, so everything left of it is finished output.
• When read finds an element worth keeping, it gets copied to position write and write advances.

The copy is safe because write never runs ahead of read. The destination has always been read already, so nothing unvisited gets overwritten.

One pass gives O(n) time and O(1) space. Remove-duplicates-from-sorted-array, move-zeros, and remove-element are all this exact loop with a different test for worth keeping.

move_zeros in place

Non-zeros move forward to the write boundary, then the tail is filled with zeros.

def move_zeros(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0
    return nums

print(move_zeros([0, 4, 0, 3, 12]))
print(move_zeros([0, 0, 1]))

Output

[4, 3, 12, 0, 0]
[1, 0, 0]

The first loop is the reader-writer pattern with nums[read] != 0 as the keep test. Non-zeros land at consecutive positions from the front, and their relative order survives because they are copied in the order they were read.

After that loop, write holds the count of non-zeros, which is exactly where the zeros begin. The second loop needs no other information.

The two loops together touch each position at most twice, so this is O(n) with no second list allocated anywhere.

The second call is worth tracing. Both leading zeros are skipped, the 1 is written to position 0, and write ends at 1, so positions 1 and 2 get filled with zeros.