Two Sum Interview: All 3 Approaches Explained

Short answer: in a Two Sum interview, state the O(n²) brute force first, then solve it in one pass with a hash map that stores each value's index and checks for target - num before inserting. That is O(n) time and O(n) space. Use two pointers instead if the array is already sorted.

Two Sum is the "hello world" of coding interviews, which does not make it free points. Interviewers use it to see whether you clarify the variant, explain trade-offs, and handle duplicates. This page covers all three standard approaches and what to say for each.

Problem (classic form): Given an integer array nums and an integer target, return indices i and j such that nums[i] + nums[j] == target. Assume exactly one solution exists, and you may not use the same element twice.

Variants exist: the array is sorted, you return values instead of indices, or you return all pairs. Ask which one you have before writing code.

Approach 1: Brute force

Check every pair (i, j) with i < j.

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

Time: O(n²)
Space: O(1) extra

What to say: "The naive approach checks every pair. That is quadratic time and constant space. Let me see if we can do better."

Saying this out loud shows you have a correct baseline before reaching for the trick, and it gives you something to fall back on if the optimisation goes wrong.

Approach 2: Sort, then two pointers

Build a list of (value, original_index) pairs and sort it by value. Put one pointer at each end. If the sum is too small, move the left pointer right; if it is too big, move the right pointer left.

def two_sum(nums, target):
    pairs = sorted((num, i) for i, num in enumerate(nums))
    left, right = 0, len(pairs) - 1
    while left < right:
        total = pairs[left][0] + pairs[right][0]
        if total == target:
            return [pairs[left][1], pairs[right][1]]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

Time: O(n log n), dominated by the sort
Space: O(n) for the pairs list

Caveat: sorting loses the original positions, which is why you carry the index along. Because the two pointers are always at different positions, you never use the same element twice, even when values repeat.

When it wins: the input is already sorted (then you skip the sort and get O(n) time and O(1) space), or the interviewer asks you not to use a hash map.

Approach 3: One-pass hash map (the usual answer)

For each number, check whether target - num has already been seen. If it has, return both indices. If not, store num -> index and move on.

def two_sum(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: O(n) on average
Space: O(n) for the map

What to say: "I am trading space for time. Each lookup is O(1) expected, so this is a single pass."

Pitfall: duplicate values

With nums = [3, 3] and target = 6, a map from value to index can only hold one index per value. This still works because you check for the complement before inserting the current element. At i = 1, the map already holds 3 -> 0, so you return [0, 1]. If you inserted first and checked second, you could match an element with itself, for example nums = [3, 2, 4] with target = 6 would wrongly return [0, 0].

Comparison

Approach	Time	Extra space	Use when
Brute force	O(n²)	O(1)	Stating a baseline
Sort + two pointers	O(n log n)	O(n)	Sorted input, or no hash map allowed
Hash map	O(n)	O(n)	Default for unsorted input that needs indices

Follow-ups to expect

Return all pairs that sum to the target, without duplicate pairs in the output.
The array is sorted: O(n) time and O(1) space with two pointers on the original array.
3Sum and 4Sum: sort, fix one element, then run two pointers on the rest. Try 3Sum next.
The data does not fit on one machine: an external sort or a partition-by-hash sketch. This is rare in phone screens.

Putting it together in the interview

Clarify duplicates, whether the input is sorted, and what to return.
State the brute force, then improve on it.
Implement the hash map (or the version that fits the variant).
Trace a short example, including a duplicate case like [3, 3].
State the complexity and mention when two pointers would be better.

The five lines of code are not really the point. The interviewer is watching the structure: clarify, baseline, improve, test, analyse. You will reuse that same structure on harder graph and DP problems. For more on narrating it, see thinking out loud in coding interviews and the time complexity cheat sheet. How the AI evaluates shows how TechInView scores each of those steps.

Practice problemEasyarrays

Two Sum

googleamazonmeta+2

Open the problem

The Complete Guide to Two Sum (All 3 Approaches)