How Do You Solve Two Sum?

The efficient approach is a single pass with a hash map. As you walk the array, ask a simple question: have I already seen the number that would complete the pair? Store each value and its index as you go, and check for the complement before you store the current value, which guarantees you never reuse the same element twice.

def two_sum(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return seen[complement], i
        seen[value] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))

The outputs are the index pairs zero and one, and one and two. The second example is the one that catches people: the pair is three plus three is not it, but two plus four is, so the correct answer is indices one and two rather than the naive pairing of the first three with the four.

The mechanism is what makes it linear rather than quadratic. A brute force approach tries every pair and costs O of n squared. The map replaces the inner search with a constant-time lookup, so each element is visited once and the total is O of n time with O of n space.

The trade-off to name is that you pay in memory for the speed, and you give up the sorted-input shortcut that lets you solve it in O of 1 extra space. Also note the ordering rule: because you check for the complement before inserting the current value, you can never return the same index twice, which matters when the target is twice a single element, for example two plus two equals four.

Yes, and you should, because sorting gives you a structural advantage you can exploit. Place one pointer at each end of the array and compare their sum to the target. If the sum is too small, the left pointer can only move right, since moving it left would make the sum even smaller. If the sum is too large, the right pointer can only move left. That is the two pointers technique, and it runs in O of n time with O of 1 extra space.

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

print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 2, 3, 4, 5], 99))

The first call prints the pair zero and one. The second prints nothing but None, because the largest possible sum is nine, which is short of ninety-nine, and the pointers walk all the way to the middle before the loop ends. That second case is a good thing to show: it demonstrates that the function handles the no-solution case cleanly instead of looping forever.

The trade-off against the hash map version is the precondition. This approach needs the array sorted, and if it is not sorted the ordering guarantee is gone and the pointer movements can skip the answer. Sorting a copied array would cost O of n log n time and O of n space, which is more than the map version needs, so the two pointers method only wins when the data is already sorted or when you will reuse the sorted order for many queries.

Finding every pair rather than one pair costs O of n squared in the worst case, because there can be O of n answers, and simply reporting them already requires that much output. The counting argument is the honest one: if the input is n copies of the same value and the target is twice that value, there are n times n minus one over two distinct pairs, and any algorithm must at least touch that many pieces of information.

The algorithm itself is a small extension of the two pointers idea. Sort the input, then for each starting index run a second scan with two pointers looking for the complement. The outer loop fixes one element and the inner loop finds every partner for it, and you skip duplicates to avoid reporting the same pair more than once. The result is O of n squared time, plus the O of n log n sort, with O of n space for the output and the working copy.

If you instead keep the hash map approach and only look back at previously seen elements, you still get O of n squared total time, but you can avoid the sort and report pairs in the order they are discovered. The output size dominates either way, which is the point: the jump from linear to quadratic is caused by the number of answers, not by a worse inner loop.

The trade-off worth mentioning is that interviewers often ask for all pairs specifically to see whether you distinguish between finding one answer and enumerating many. A candidate who writes a linear single-pass solution and returns early has answered a different question, and the interesting follow-up is always: what changes when you must report all of them?