Two pointers

Two indexes, moving through a list toward each other or in the same direction, can replace a nested loop. The pattern works when each step can safely throw away some possibilities.

Opposite ends: pairs in a sorted list

In a sorted list, find two numbers that add up to a target.

Start with left at the smallest number and right at the largest. If their sum is too small, the only way to grow it is to move left up; if too big, move right down. Each step rules out one number for good, so the whole search is O(n), with O(1) extra space. (The Python course's two-pointers lesson works this one through.)

The same idea checks a palindrome: compare the outer characters, and move both pointers inward.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():          # skip spaces and punctuation
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

print(is_palindrome("Was it a car, or a cat I saw?"))
print(is_palindrome("race a car"))

This version skips anything that is not a letter or digit, and ignores capitals, as interview versions of the problem usually ask. Clarify that in step 1!

Same direction: in-place changes

Remove the duplicates from a sorted list in place, and return the new length.

A slow pointer marks where the next kept value goes; a fast pointer reads every value. Copy a value only when it differs from the last one kept:

def remove_duplicates(nums):
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1 if nums else 0

Three sum

Find all the different triples that add up to 0.

Sort the list. For each number a, solve "two numbers that add up to −a" with two pointers on the rest of the list. That is O(n²), against O(n³) for three loops. The hard part is skipping duplicates, so each triple appears once:

def three_sum(nums):
    nums = sorted(nums)
    triples = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                            # the same first number again
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triples.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1                   # skip repeated middle numbers
                right -= 1
    return triples

print(three_sum([-1, 0, 1, 2, -1, -4]))

The container with the most water

Vertical lines of heights h[i]; two of them, with the x-axis, form a container. Which holds the most water? The area is min(h[l], h[r]) × (r − l). Start at both ends and always move the shorter line inward: moving the taller one can never help, because the width shrinks and the height is still limited by the shorter line. O(n).

Mark lesson complete