Two Pointers Technique (With Python Examples)

The two pointers technique walks through a sequence with two indexes at once instead of one. Used well, it turns many O(n²) "check every pair" solutions into O(n), with O(1) extra memory.

There are two main shapes:

• opposite ends: one pointer starts at the left, one at the right, and they move toward each other;
• same direction: both start at the left, one moving faster or ahead of the other.

Opposite ends: pair sum in a sorted list#

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

Start with the smallest and largest. If their sum is too small, the only way to increase it is to move the left pointer right. If it is too big, move the right pointer left.

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

print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))
print(pair_with_sum([1, 3, 4, 6, 8, 11], 20))

(4, 6)
None

Each step moves one pointer, so there are at most n steps: O(n) time and O(1) space, compared with O(n) space for the hash table version. It only works because the list is sorted.

Same direction: removing duplicates in place#

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

A slow pointer marks where the next unique value goes; a fast pointer scans ahead:

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

data = [1, 1, 2, 3, 3, 3, 4]
length = dedupe_sorted(data)
print(length, data[:length])

4 [1, 2, 3, 4]

Merging two sorted lists#

One pointer per list. Repeatedly take the smaller front item:

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

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

[1, 2, 3, 4, 9, 10, 12]

O(n + m) time. This is the heart of merge sort.

Container with most water#

Lines of heights h stand at positions 0, 1, 2, …. Pick two lines that, with the x-axis, hold the most water.

The water held is min(h[l], h[r]) × (r − l). Start with the widest pair. Moving the taller line inward can never help (the shorter one still limits the height while the width shrinks), so always move the shorter one:

def max_water(h):
    left, right = 0, len(h) - 1
    best = 0
    while left < right:
        best = max(best, min(h[left], h[right]) * (right - left))
        if h[left] < h[right]:
            left += 1
        else:
            right -= 1
    return best

print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))

49

The best pair is the 8 at index 1 and the 7 at index 8: height 7 × width 7 = 49.

When to reach for two pointers#

• the input is sorted (or you can sort it) and you look for pairs or triples;
• you must work in place with O(1) memory;
• you compare items from both ends (palindromes, reversing);
• you merge or compare two sequences.

Common mistakes#

Practice#

def three_sum_zero(nums):
    nums = sorted(nums)
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                       # same first value: skip
        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:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1              # skip duplicates
    return result

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

[[-1, -1, 2], [-1, 0, 1]]
[[0, 0, 0]]

Key takeaway#

Next: a pointer pair that tracks a moving range, the Sliding Window.