DSA Two Pointers

The problem

Two Sum II gives a sorted list of numbers and a target. The task is the positions of the two values that add to the target. Positions count from 1, and exactly one pair is promised in the main cases.

Sorted is the key fact in the input. The order lets each step discard one end of the list for good. That discarding is the two pointers pattern, and this problem is its spine.

cases = [
    ([2, 7, 11, 15], 9, (1, 2)),
    ([2, 7, 11, 15, 20], 26, (3, 4)),
    ([1, 3, 5, 8, 9], 12, (2, 5)),
    ([-3, 0, 3, 5], 0, (1, 3)),
]
for nums, target, expected in cases:
    print(nums, 'target', target, 'positions:', expected)

Intuition

Two pointers are two indices in one list. One starts at the first value. One starts at the last value.

The first try pairs the two ends. That pair gives the smallest value with the largest value. Its sum points the way: too small means the small end must grow, and too big means the large end must shrink.

nums = [2, 7, 11, 15, 20]
target = 26
left = 0
right = len(nums) - 1
total = nums[left] + nums[right]
print('first pair:', nums[left], '+', nums[right], '=', total)
print('target:', target)
print('sum too small, so the left pointer must move right')

Brute force

The brute force ignores the order. It pairs every first value with every later value. Each pair gets one sum and one comparison.

def two_sum_brute(nums, target):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] + nums[j] == target:
                return (i + 1, j + 1), checks
    return None, checks

for nums, target in [([2, 7, 11, 15], 9), ([2, 7, 11, 15, 20], 26)]:
    result, checks = two_sum_brute(nums, target)
    print(nums, 'target', target, 'positions:', result, 'checks:', checks)

The brute force finds the pair. It also rechecks values that a sorted list could have ruled out. The pointer scan rules out one end per step.

The optimal solution: pointers closing in

The key idea is one comparison per step. A sum below the target moves the left pointer right, and a sum above the target moves the right pointer left.

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

cases = [
    ([2, 7, 11, 15], 9),
    ([2, 7, 11, 15, 20], 26),
    ([1, 3, 5, 8, 9], 12),
    ([-3, 0, 3, 5], 0),
]
for nums, target in cases:
    print(nums, 'target', target, 'positions:', two_sum_sorted(nums, target))

Walkthrough

Take [2, 7, 11, 15, 20] with target 26. The pointers start on 2 and 20. Each line below is one tried pair.

nums = [2, 7, 11, 15, 20]
target = 26
left = 0
right = len(nums) - 1
while left < right:
    total = nums[left] + nums[right]
    print('try', nums[left], '+', nums[right], '=', total)
    if total == target:
        print('found at positions', left + 1, 'and', right + 1)
        break
    if total < target:
        left += 1
    else:
        right -= 1

The sum 22 is too small, so the left pointer moves. The sum 27 is too big, so the right pointer moves. Four pairs reach the answer, and no pair is tried twice.

Complexity

Time is O(n). Each step moves one pointer inward, and a pointer never moves back.

Space is O(1). Two indices and one sum are the only extra storage.

def brute_checks(n):
    return n * (n - 1) // 2

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

for n in [10, 20, 40]:
    nums = list(range(1, n + 1))
    print('n =', n, 'brute worst checks:', brute_checks(n), 'pointer worst checks:', pointer_checks(nums, 1000000))

Edge cases and pitfalls

A list with no matching pair ends with the pointers meeting. The function then returns None. Callers must handle None before reading positions from it.

Positions are the classic off-by-one trap. The indices are zero-based inside the code. The answer for this problem is one-based, so each index gains one on return.

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

print('two values:', two_sum_sorted([3, 4], 7))
print('no pair:', two_sum_sorted([1, 2, 3], 100))
print('duplicates:', two_sum_sorted([2, 2, 5], 4))
print('negatives:', two_sum_sorted([-5, -1, 0, 4], -1))