Introduction

The “two sum” problem asks whether any two elements in an array add up to a target k, and often also asks you to return the pair or their indices. The brute-force solution is easy to write, but the standard efficient solution uses a hash set or hash map and runs in linear time on average. The right version depends on whether you need values, indices, or all matching pairs.

Brute Force Baseline

The simplest solution checks every pair.

1def two_sum_bruteforce(nums, target):
2    for i in range(len(nums)):
3        for j in range(i + 1, len(nums)):
4            if nums[i] + nums[j] == target:
5                return i, j
6    return None
7
8print(two_sum_bruteforce([2, 7, 11, 15], 9))

This works, but it is O(n^2), which becomes expensive as the array grows.

Standard Efficient Solution with a Hash Map

If you need indices, store seen values and their indices as you scan left to right.

1def two_sum(nums, target):
2    seen = {}
3
4    for i, value in enumerate(nums):
5        needed = target - value
6        if needed in seen:
7            return seen[needed], i
8        seen[value] = i
9
10    return None
11
12print(two_sum([2, 7, 11, 15], 9))   # (0, 1)
13print(two_sum([3, 2, 4], 6))        # (1, 2)

This is the usual interview-quality answer: O(n) average time and O(n) extra space.

Why the Hash Map Order Matters

The lookup must happen before storing the current value if you want to avoid using the same element twice incorrectly.

For example:

print(two_sum([3, 3], 6))

This works because the first 3 is stored, then the second 3 sees that it needs another 3 and finds the earlier index.

If you structure the logic carelessly, duplicate handling becomes buggy.

Return Values Instead of Indices

If the task asks for the two values rather than their positions, a set can be enough.

1def two_sum_values(nums, target):
2    seen = set()
3
4    for value in nums:
5        needed = target - value
6        if needed in seen:
7            return needed, value
8        seen.add(value)
9
10    return None
11
12print(two_sum_values([10, 1, 8, 3], 11))

This is slightly simpler because you do not need to preserve indices.

Sorted Array Variant

If the array is already sorted, a two-pointer solution is often cleaner.

1def two_sum_sorted(nums, target):
2    left, right = 0, len(nums) - 1
3
4    while left < right:
5        current = nums[left] + nums[right]
6        if current == target:
7            return left, right
8        if current < target:
9            left += 1
10        else:
11            right -= 1
12
13    return None
14
15print(two_sum_sorted([1, 2, 4, 7, 11], 9))

This runs in O(n) time and O(1) extra space, but it depends on sorted input.

If You Need All Pairs

Returning one match is simpler than returning every valid pair. If you need all distinct pairs, define clearly whether duplicates in the input should create duplicate outputs.

For example:

1def all_pairs(nums, target):
2    seen = set()
3    pairs = set()
4
5    for value in nums:
6        needed = target - value
7        if needed in seen:
8            pairs.add(tuple(sorted((value, needed))))
9        seen.add(value)
10
11    return pairs
12
13print(all_pairs([1, 5, 7, -1, 5], 6))

This returns unique value pairs, not every index-level combination.

Edge Cases

You should think about:

• duplicate values
• negative numbers
• zero
• no solution
• whether using the same element twice is forbidden

The standard formulation requires two distinct elements, so one array element cannot satisfy the target by pairing with itself unless it appears at least twice.

Space-Time Tradeoff

The two common efficient strategies are:

• hash map: O(n) time, O(n) space
• sorting plus two pointers: O(n log n) time if sorting is needed, O(1) extra space on top of the array

If the input is unsorted and you need original indices, the hash-map solution is usually the best fit.

Common Pitfalls

The biggest mistake is forgetting that the two elements must usually be distinct positions, not just values. Another is mishandling duplicates such as [3, 3] for target 6. Developers also often choose the sorted two-pointer approach without realizing it destroys original index positions unless they preserve them separately. Finally, if the problem asks for all pairs, reusing the one-pair hash-map solution without clarifying duplicate semantics usually leads to ambiguous output.

Summary

• The brute-force solution checks all pairs and costs O(n^2).
• The standard efficient solution uses a hash map and runs in O(n) average time.
• Use a set if you only need matching values, not indices.
• Use two pointers when the input is already sorted.
• Be explicit about duplicate handling and whether you need one pair or all pairs.