Two pointers

Why two pointers

A pointer here is just an index that marks a position. Two-pointer techniques move two indexes through an array so that each step rules out a whole group of answers. They often turn an O(n²) "try every pair" into one O(n) pass with O(1) extra space. There are two main shapes: pointers at opposite ends moving towards each other, and two pointers moving in the same direction at different speeds.

Opposite ends: a pair with a target sum

In a SORTED array, put left at the start and right at the end. If nums[left] + nums[right] is too small, the only way to grow the sum is to move left forward. If it is too big, move right back. If it equals the target, you are done.

Why no pair is missed: when the sum is too small, nums[left] plus the LARGEST value still available is too small, so nums[left] cannot be part of any answer and can be dropped. The same argument drops nums[right] when the sum is too big. Every step drops one item, so there are at most n steps: O(n) time and O(1) space. The hash map from Topic 1 is also O(n) time, but it needs O(n) space; two pointers need sorted input.

def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1
        else:
            right -= 1
    return []

print(pair_sum([1, 3, 4, 6, 9], 10))   # Output: [0, 4]
print(pair_sum([1, 3, 4, 6, 9], 8))    # Output: []

Container with most water

heights[i] is the height of a vertical line at position i. Two lines and the ground form a container that holds min(heights[l], heights[r]) × (r − l) units of water. Start with the widest container (l = 0, r = n − 1), record its area, then move the pointer at the SHORTER line inwards. Moving the taller one can never help: the width shrinks and the height is still capped by the same shorter line. O(n) time, O(1) space.

For heights [1, 8, 6, 2, 5, 4, 8, 3, 7] the best container uses the 8 at index 1 and the 7 at index 8: min(8, 7) × (8 − 1) = 49.

Same direction: slow and fast pointers

Here both pointers move left to right. The fast (read) pointer looks at every item; the slow (write) pointer marks where the next kept item goes. This is the write-pointer pattern from Module 2, and it filters an array in place in O(n) time and O(1) space. Problems usually ask you to return k, the number of kept items, and promise to look only at nums[:k].

def remove_value(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write            # nums[:write] holds the kept items

a = [3, 2, 2, 3, 4]
k = remove_value(a, 3)
print(k, a[:k])   # Output: 3 [2, 2, 4]

To remove duplicates from a SORTED array, only the test changes: equal values sit next to each other, so keep nums[read] when it differs from the last kept item, nums[write − 1].

Merging two sorted arrays

Put one pointer at the start of each sorted array. Repeatedly take the smaller of the two front items and move that pointer on. When one array runs out, copy the rest of the other. Each step moves one pointer, so merging arrays of sizes n and m is O(n + m). This merge is the heart of merge sort (Module 6) and of merging sorted linked lists (Module 4).

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

print(merge([1, 4, 9], [2, 3, 10, 12]))   # Output: [1, 2, 3, 4, 9, 10, 12]

3-sum: sort, fix one, two-pointer the rest

To find all unique triplets that sum to 0, sort first (O(n log n)). Then, for each index i, look for pairs to the right of i that sum to −nums[i] with the opposite-ends walk. That is O(n) for each i, so O(n²) in total, much better than O(n³) for checking all triples.

Duplicates are the tricky part. Skip i when nums[i] == nums[i − 1], because the same first value would give the same triplets again. After finding a triplet, move left past every copy of its value and right past every copy of its value before continuing. You can also stop early when nums[i] > 0: every later number is at least as big, so no sum can reach 0.

Common mistakes

• Using opposite-end pointers on an UNSORTED array. Fix: sort first (and remember that sorting changes the indexes), or use a hash map.
• Writing while left <= right in pair sum, which can pair an item with itself. Fix: while left < right.
• Moving the taller line in container with most water. Fix: always move the shorter one.
• Forgetting to skip duplicates in 3-sum, so the same triplet appears twice. Fix: skip equal values for i, and after each match move past equal values on both sides.
• Returning the list instead of the new length k when filtering in place, or reading items beyond k. Fix: return k and use only nums[:k].