Find All Pairs That Sum to a Target: Two Pointer and Hash Set Approaches

Given a list of integers and a target sum, find all unique pairs whose values add up to the target. This is the “two sum — return all pairs” variant, and it is worth knowing three different implementations with their trade-offs.

Approach 1: Brute Force — O(n²)

Check every possible pair. Simple to write, but not what you want for large inputs.

def find_pairs_brute(arr, target):
    """Return all unique pairs (a, b) where a + b == target and a <= b."""
    pairs = set()
    n = len(arr)

    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                pair = (min(arr[i], arr[j]), max(arr[i], arr[j]))
                pairs.add(pair)   # set avoids duplicates

    return sorted(pairs)

arr = [2, 4, 1, 5, 3, 8, 7, 6]
print(find_pairs_brute(arr, 9))
# Output: [(1, 8), (2, 7), (3, 6), (4, 5)]

Storing pairs as (min, max) tuples and adding them to a set handles the case where the same pair could be found in multiple orderings.

Approach 2: Hash Set — O(n)

For each element, check whether its complement (target - element) is already in a seen set. If yes, you have found a pair.

def find_pairs_hashset(arr, target):
    """O(n) pair finding using a complement lookup set."""
    seen = set()
    pairs = set()

    for num in arr:
        complement = target - num
        if complement in seen:
            pairs.add((min(num, complement), max(num, complement)))
        seen.add(num)

    return sorted(pairs)

arr = [2, 4, 1, 5, 3, 8, 7, 6]
print(find_pairs_hashset(arr, 9))
# Output: [(1, 8), (2, 7), (3, 6), (4, 5)]

One pass through the array. Each lookup is O(1). Total: O(n) time, O(n) space.

Approach 3: Two Pointers on a Sorted Array — O(n log n)

Sort the array, then use two pointers — one at the start, one at the end. Move them inward based on whether the current sum is too small or too large.

def find_pairs_two_pointer(arr, target):
    """Two-pointer approach on sorted array — O(n log n) time, O(1) extra space."""
    arr.sort()
    left = 0
    right = len(arr) - 1
    pairs = []

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            pairs.append((arr[left], arr[right]))
            # Skip duplicates from both ends
            while left < right and arr[left] == arr[left + 1]:
                left += 1
            while left < right and arr[right] == arr[right - 1]:
                right -= 1
            left += 1
            right -= 1
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return pairs

arr = [2, 4, 1, 5, 3, 8, 7, 1, 5]
print(find_pairs_two_pointer(arr, 9))
# Output: [(1, 8), (2, 7), (3, 6), (4, 5)]

The duplicate-skipping logic inside the if current_sum == target branch ensures the same pair is not reported twice when the input contains repeated values.

Handling the Case Where an Element Pairs with Itself

If the same element can be used twice (e.g. [4, 4] with target 8), the hash set approach needs a small adjustment:

def find_pairs_allow_reuse(arr, target):
    """Pairs where the same value may appear twice (if it occurs twice in arr)."""
    from collections import Counter
    freq = Counter(arr)
    pairs = set()

    for num in freq:
        complement = target - num
        if complement in freq:
            if num == complement:
                # Need at least two occurrences
                if freq[num] >= 2:
                    pairs.add((num, complement))
            else:
                pairs.add((min(num, complement), max(num, complement)))

    return sorted(pairs)

print(find_pairs_allow_reuse([4, 4, 1, 5, 3, 8], 8))
# Output: [(3, 5), (4, 4)]

Summary

Approach	Time	Space	Notes
Brute force	O(n²)	O(pairs)	Simple, avoid for large inputs
Hash set	O(n)	O(n)	Best for unsorted, general case
Two pointers	O(n log n)	O(1)*	*If sorting in-place is acceptable

The hash set version is the standard interview answer for this problem.