How to Solve the Two Sum Problem Efficiently

The Two Sum problem is one of the most common coding interview questions. It asks: given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You might assume each input has exactly one solution and you cannot use the same element twice. Let’s break down the most efficient approaches, from the simple brute force to the optimal hash map solution, and also touch on the two-pointer technique when the array is sorted.

What Is the Two Sum Problem Exactly?

Given an array nums and a target target, find two distinct indices i and j such that nums[i] + nums[j] == target. For example, if nums = [2, 7, 11, 15] and target = 9, the answer is [0, 1] because 2 + 7 = 9. This problem tests your understanding of arrays, hash maps, and time-space trade-offs.

Brute Force Approach: The Naive Solution

The most straightforward way is to check every possible pair. Use two nested loops: the outer loop picks the first number, the inner loop picks the second. If the sum equals target, return the indices. This approach is simple to implement but highly inefficient.

Here’s the code in Python:

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

Time complexity: O(n²). For each element, we loop through the rest. As the array grows, runtime grows quadratically. Space complexity: O(1) — we only store a constant amount of extra space. However, this is rarely acceptable in production or interviews due to poor performance on large datasets.

Hash Map Solution: Optimal Time Efficiency

The hash map (or dictionary) approach solves the problem in a single pass. As you iterate through the array, check if the complement (target minus current number) already exists in the map. If yes, you’ve found the pair. Otherwise, store the current number with its index. This gives O(n) time and O(n) space.

Code example:

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

Why it works: The hash map records numbers we’ve seen so far. By looking up the complement in constant time, we avoid the second loop. This is the most common answer expected in interviews.

Edge Cases to Consider

What if the array contains duplicates? The problem usually says there’s exactly one solution, so duplicates are fine as long as we return first valid pair. Our code naturally handles that: we check existence before storing the current index, so we don’t overwrite a required index. Also, consider negative numbers and zeros — the complement calculation works regardless of sign.

Two-Pointer Technique: Best for Sorted Arrays

If the input array is sorted, we can use two pointers: one at the left (smallest) and one at the right (largest). If their sum is less than target, move left pointer right; if greater, move right pointer left. Continue until they meet or we find the target sum.

Code:

def two_sum_two_pointer(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

Time complexity: O(n) for the loop, but sorting the array first would cost O(n log n) if not already sorted. Space complexity: O(1) beyond the input. This method modifies indices relative to the sorted order, so return original indices if needed — you may have to store the original positions by pairing each element with its index before sorting.

Comparing the Approaches

Method	Time Complexity	Space Complexity	When to Use
Brute Force	O(n²)	O(1)	Small arrays, teaching basic loops
Hash Map	O(n)	O(n)	General case, unsorted arrays
Two-Pointer	O(n) or O(n log n) with sort	O(1) or O(n) for index mapping	Sorted input or memory constraints

For most coding interviews, the hash map solution strikes the best balance. It handles unsorted arrays and runs in linear time. The two-pointer technique is a great follow-up if the interviewer mentions the array might be sorted.

Common Mistakes and How to Avoid Them

One frequent mistake is forgetting that you cannot use the same element twice. In the hash map solution, ensure you check the complement before storing the current number, so you don’t pair an element with itself. Another pitfall is returning indices in the wrong order; the problem usually doesn’t care, but it’s safe to return them in ascending order.

If you use the two-pointer approach on an unsorted array without sorting first, you’ll get wrong results. Always clarify assumptions upfront. Also, note that the hash map solution uses extra memory; if the interviewer asks for constant space, you might need to sort first or accept O(n) space.

Variations of the Two Sum Problem

Once you master Two Sum, you’ll encounter similar problems:

• Two Sum II: Input array is sorted; use two-pointer.
• Two Sum III: Design a data structure that supports adding numbers and finding if a pair sums to target.
• Three Sum: Find all triplets that sum to zero. This builds on Two Sum.

Understanding the core pattern of using a hash map for complement lookup will help solve many variations. For a deeper dive into related data structures, check out our guide on How to Implement a Trie for Autocomplete, which also relies on efficient lookups.

What to Do When the Two Sum Problem Has Multiple Solutions?

Sometimes the problem asks for all pairs, not just one. In that case, the hash map approach can be extended to collect all pairs. Instead of returning on first match, add each pair to a list and continue. Be careful with duplicates: if the array has duplicate numbers, you might need to handle them separately. A common trick is to track indices in the hash map as lists. For the two-pointer approach on sorted arrays, you can move both pointers inward after finding a pair to collect all.

How to Handle Very Large Inputs

If the array is too large to fit in memory, you might need to process it in chunks. For a stream of numbers, a hash map that stores only seen values works well, but you must ensure you have enough memory. Alternatively, if you can sort the data externally, the two-pointer technique uses constant memory. Another trick for extremely large arrays with a small value range is to use a bitset or boolean array as a compact hash map.

Conclusion

The Two Sum problem is a gateway to understanding algorithmic trade-offs. Start with brute force to understand the problem, then move to the hash map solution for efficiency. If the array is sorted, the two-pointer technique offers constant space. Practice these solutions until they become second nature. Next time you see a problem involving pair sums, you’ll know exactly which tool to use.

Frequently asked questions

What is the Two Sum problem?

The Two Sum problem asks you to find two numbers in an array that add up to a given target. You return their indices. It’s a common coding interview problem that tests basic algorithm skills.

What is the best time complexity for Two Sum?

The best time complexity is O(n), achieved using a hash map. You iterate once, checking for the complement in the map. This is optimal because you need to examine each element at least once.

Can you solve Two Sum without extra space?

Yes, if the array is sorted, you can use the two-pointer technique with O(1) extra space. If unsorted, you can sort first (O(n log n)) then use two pointers, but that changes the indices.

How does the hash map solution work?

As you iterate, you store each number and its index. For each element, you compute the complement (target minus current number). If the complement exists in the map, you found the pair and return their indices.

What if the array contains duplicates?

Most versions assume a single solution, so duplicates are fine. The hash map solution handles them by checking the complement before storing the current index, ensuring you don’t use the same element twice.

Is the Two Sum problem hard?

It’s considered easy to medium depending on the constraints. The brute force is trivial, but the optimal solution requires understanding hash maps. It’s a good entry-level interview question.

What is the two-pointer technique for Two Sum?

The two-pointer technique uses a left and right pointer on a sorted array. If the sum is too low, move left right; if too high, move right left. It finds a pair in O(n) time after sorting.

How do I handle the Two Sum problem if I need to return all pairs?

For all pairs, extend the hash map to store lists of indices. When you find a complement, add all combinations. For two-pointer on sorted array, continue scanning after finding a pair to collect all.