Two Sum Problem: Multiple Approaches Explained

The fastest way to solve Two Sum is one pass with a hash map: for each number, check whether its complement (target minus the current value) is already stored, and if not, store the current value with its index. That runs in linear time and linear space, versus the quadratic time of the brute-force scan that checks every pair.

Two Sum shows up constantly in interviews because it is the cleanest way to watch a hash map trade memory for speed. Here are three approaches, from the naive version to the one you should actually submit.

What is the Two Sum problem asking?

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input has exactly one solution, and you may not use the same element twice.

Example.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Two constraints do most of the interviewing work here. First, the answer is a pair of positions, not the values themselves, so any solution that reorders the array has to be careful about what it returns. Second, the same element cannot be reused, so a value that is exactly half of the target only counts if it appears twice. Keep both in mind, because almost every wrong answer to this problem trips on one of them.

How slow is the brute-force solution?

The simplest approach checks every pair of numbers.

def twoSum(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]
    return []

Time complexity is O(n²).

Space complexity is O(1).

It always works, but it slows down fast as the array grows, so treat it as the version you state and then improve, not the one you submit. The inner loop starts at i + 1 on purpose. That is what keeps you from pairing an element with itself and from checking the same pair twice, and it is the first thing to get right before you optimize anything.

The cost grows with the square of the input. Double the array and the work roughly quadruples. On a handful of elements that is invisible, but the arrays you actually get in an interview are large enough that a quadratic scan is the difference between an answer that returns instantly and one that hangs. The point of stating brute force out loud is to show you can see the pair-checking structure. The point of moving past it is to show you know the structure is wasteful.

What is the fastest way to solve Two Sum?

Use a hash map to remember every number you have already seen, keyed by value with its index as the payload. For each new number, look up its complement in a single step.

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

Time complexity is O(n).

Space complexity is O(n).

This is the optimal solution for the general, unsorted case. You make one pass, and each lookup and insert is average O(1). The move that makes it work is subtle: we check for the complement *before* we store the current number. That ordering is what guarantees we never pair an element with itself, and it also handles duplicate values without any special case.

Walk it on nums = [3, 2, 4], target = 6, where the answer is [1, 2] and the naive "first two numbers" guess is wrong.

• We see 3 at index 0. The complement is 3. Nothing is stored yet, so we record 3 -> 0 and move on.
• We see 2 at index 1. The complement is 4. Not stored, so we record 2 -> 1.
• We see 4 at index 2. The complement is 2, and 2 is already in the map at index 1. We return [1, 2].

Notice what never happened. We never went back to re-scan earlier elements. Each number was touched once, and every question we asked ("have I already seen the number I need?") was answered by a single lookup instead of a loop. That is the whole trade: we spend memory to hold what we have seen so that we never have to look at it again.

The same ordering rescues the tricky case nums = [3, 3], target = 6. The first 3 finds nothing and gets stored as 3 -> 0. The second 3 looks up its complement 3, finds index 0, and returns [0, 1]. Two equal values sitting at different indices, and nothing gets reused. If we had stored before checking, the first 3 would have found itself and returned a bogus [0, 0].

One honest footnote on the complexity: hash lookups are O(1) on average, not guaranteed. Pathological inputs can collide and degrade a lookup toward linear time, which would drag the whole solution back toward quadratic in the worst case. In practice, and in every interview, the average-case bound is the one that matters, and this is still the answer to give. It is worth being able to name the caveat if asked, because it shows you know the difference between amortized and worst-case behavior rather than reciting O(1) as a spell.

When should you use two pointers instead?

If the array is already sorted, you can drop the hash map and walk inward from both ends.

def twoSum(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
    return []

Time complexity is O(n log n) if you must sort first, or O(n) if the input is already sorted.

Space complexity is O(1) for the two-pointer walk itself, plus whatever the sort needs if you sort.

The logic leans entirely on the array being ordered. When the current sum is too small, the only way to grow it is to move the left pointer right toward larger values. When the sum is too big, we shrink it by pulling the right pointer left. Each step rules out one number for good, so the two pointers meet after a single pass.

One catch: sorting scrambles the original positions, so use two pointers when the array arrives sorted or when the problem asks for the values rather than their original indices. If the classic problem wants indices and you sort to use two pointers, you now have to map results back to where they started, which usually costs you the space you were trying to save. In that situation the hash map is simply the better tool.

The complexity story, in plain words

Big-O is a shorthand, so it helps to say out loud what each approach actually does as the input grows.

Brute force does work proportional to the number of pairs. With n elements there are about n²/2 pairs, and in the worst case you look at most of them, so the running time climbs with the square of the input while memory stays flat.

The hash map does a fixed amount of work per element (one subtraction, one lookup, maybe one insert), so total time grows in step with the input rather than its square. The cost shows up as memory: in the worst case, where the match is the very last pair, the map holds nearly every element you have seen.

Two pointers do the least work of all when the array is already sorted, one linear pass with no extra memory. The catch hides in that "already sorted." If you pay for the sort yourself, the sort dominates and the whole thing runs in O(n log n), which is slower than the hash map's linear pass.

Read the table one way and the hash map looks worse than two pointers on space. Pose the problem the way interviews actually do, unsorted input with indices required, and the hash map wins outright: it is the only approach that hits linear time without asking you to reorder the data first.

Edge cases the interviewer is checking for

• A value that is half the target. With target = 8 and a single 4 in the array, there is no answer, and the check-before-store ordering keeps you from pretending the lone 4 pairs with itself.
• Duplicate values. As shown above, two equal numbers are a valid pair as long as they sit at different indices. The hash map handles this for free.
• Negative numbers and zero. Complements can be negative, and target can be zero or negative. None of the approaches care, because subtraction and hash lookups do not treat sign specially. It is worth confirming your reasoning still holds, since a surprising number of first attempts quietly assume positive input.
• No valid pair. The canonical problem promises exactly one solution, but a defensive return at the end is cheap insurance and signals that you thought about the empty case.

Common mistakes

The most common bug is storing each number in the map before checking for its complement. Flip the order and any element equal to half the target will match itself and return the same index twice.

The second is returning the values instead of the indices, or the other way around. Re-read what the prompt asks for before you write the return statement, because both are plausible and only one is correct.

The third shows up when people force two pointers onto the unsorted, index-returning version of the problem. Sorting to enable the two-pointer walk throws away the original positions, and recovering them costs extra bookkeeping that usually erases the advantage. If the input is not already sorted and the answer must be indices, reach for the hash map instead.

The last is an off-by-one in brute force: starting the inner loop at i rather than i + 1, which lets an element pair with itself. It is a small slip that produces confidently wrong output on exactly the inputs an interviewer likes to try.

When to reach for this pattern

1. Brute force always works but is usually too slow at interview scale; state it, then improve it.
2. Hash maps shine on unsorted arrays when you need fast lookups, which is the default Two Sum setup.
3. Two pointers are a great fit when the array is already sorted or sortable cheaply and you can return values rather than original indices.

Pattern recognition is the real goal here. The complement trick, remember what you have seen so a future lookup is instant, generalizes far past this one problem. It powers "does a pair sum to k," "has this value appeared before," anagram grouping, and a long tail of array and string questions that all reduce to the same move. Once you can spot when a lookup table beats a nested loop, that whole family starts to look like one problem wearing different clothes, and Two Sum is the cleanest place to learn to see it.