Editor

Two pointers in Python

The two pointers technique finds a pair with a given sum in a sorted list by starting one pointer at each end and moving them inwards, one step at a time, instead of trying every pair.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. The list is sorted, so left starts at the smallest value and right at the biggest.
  2. If nums[left] + nums[right] is smaller than target, move left one step right to make the sum bigger.
  3. If the sum is too big, move right one step left to make it smaller.
  4. Stop when the sum equals target, or when the pointers meet: then no pair exists.

What to watch

  • Watch total go above and below 10 as the pointers take turns moving inwards.
  • Watch each move rule out one value for good: 14 cannot pair with anything, because even 1 + 14 is too big.
  • Watch the pointers stop at 4 and 6 after six checks, where trying every pair could take 21.

The code

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          # need a bigger sum
        else:
            right -= 1         # need a smaller sum
    return None                # the pointers met: no pair

data = [1, 3, 4, 6, 8, 11, 14]
print(pair_with_sum(data, 10))
Output
(4, 6)

Open it in the editor · Python Program to Find Pairs with a Given Sum, explained