Statement

Given an array of integers nums and a target integer target, return the indices of the two numbers in the array that add up to target. You may assume exactly one solution exists, and you may not use the same element twice. The answer can be returned in any order.

Examples

nums   = [2, 7, 11, 15]
target = 9
→ [0, 1]   because nums[0] + nums[1] == 9

nums   = [3, 2, 4]
target = 6
→ [1, 2]

nums   = [3, 3]
target = 6
→ [0, 1]

Constraints

2 ≤ len(nums) ≤ 10^4
-10^9 ≤ nums[i] ≤ 10^9
-10^9 ≤ target ≤ 10^9
Exactly one valid pair exists.

What the problem is really testing

Two Sum is not about arithmetic; it is about recognising the seen-so-far pattern. The O(n²) brute-force solution is obvious; the O(n) solution requires you to reframe the question from "is there a pair?" to "has the complement of the current element already passed by?" That reframe is the single most useful habit in array problems.

Hints

Start with the obvious. Two nested loops find the pair in O(n²). Make sure that works before optimising. Many interview candidates optimise too early and produce an incorrect O(n) solution.
Reframe the question. For each element x, what value would pair with it? Call that the complement. If you have already seen the complement, you have your pair.
Which data structure answers "have I seen X?" in O(1)? A hash map. Store each element's index as you iterate; query the map for the complement before storing.
Order matters. Query first, then insert. Otherwise an element can pair with itself when target == 2·x.

Solution: three approaches

Approach 1 · Brute force: O(n²) time, O(1) space

Try every pair. Correct, but too slow for the upper constraint of 10^4: that's 10^8 comparisons, which is slow enough to time out in strict judging environments.

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

Why it works: enumerating all ordered pairs (i, j) with i < j is exhaustive. Why it's too slow: the pair count is n(n-1)/2, which is Θ(n²).

Approach 2 · Sort and two-pointer: O(n log n) time, O(n) space

Sort the array, then use converging two pointers. Catch: sorting loses the original indices, so you must carry them alongside the values.

def two_sum_sort(nums, target):
    indexed = sorted(enumerate(nums), key=lambda p: p[1])
    i, j = 0, len(indexed) - 1
    while i < j:
        s = indexed[i][1] + indexed[j][1]
        if s == target: return [indexed[i][0], indexed[j][0]]
        if s < target:  i += 1
        else:           j -= 1
    return []

This is a correct O(n log n) solution. It's occasionally the right answer (when you already need the array sorted for another reason), but for pure Two Sum, the next approach is strictly better.

Approach 3 · Hash map (seen-so-far): O(n) time, O(n) space

This is the canonical solution. Iterate once. For each element, compute the complement that would reach the target. Check whether the complement is already in the hash map; if so, return. Otherwise, record the current element and its index.

def two_sum(nums, target):
    seen = {}                    # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i              # insert AFTER the check
    return []

Why the check-then-insert order matters: consider nums = [3] and target = 6. Insert-first would store 3 → 0, then query the complement 6 − 3 = 3, find it, and (incorrectly) return [0, 0]. Check-first correctly falls through: the map is empty when we query, so nothing matches.

Complexity: one pass, one hash lookup per element. Hash lookup is expected O(1), so total expected time is O(n). Worst-case O(n²) under adversarial hashing, but Python's randomised hashing prevents that in practice. Space O(n) for the map in the worst case where no pair exists until the last element.

Complexity comparison

Approach	Time	Space	Notes
Brute force	O(n²)	O(1)	Too slow for n ≥ 10⁴
Sort + two-pointer	O(n log n)	O(n)	Good when array is sorted already
Hash map	O(n) expected	O(n)	Canonical answer

Edge cases to verify

Pair at the extremes: nums = [1, 9], target = 10.
Target equals double an element: nums = [3, 3], target = 6. The check-then-insert order is exactly what makes this work.
Negative numbers: nums = [-3, 4, 3, 90], target = 0. No special handling needed; the hash map doesn't care about sign.
No solution: the problem says one exists, but defensive code should return [] rather than crashing.

Where beginners go wrong

Inserting before querying. Produces wrong answers when target = 2·x. The fix is one line reorder.
Storing values as keys and indices as values (or the reverse) inconsistently. Pick one convention and don't mix it. seen[value] = index is the more useful direction.
Returning the values instead of the indices. Read the problem carefully: it asks for indices. Most variants do.
Using list.index. That's O(n); inside a loop it makes the whole algorithm O(n²). The hash map exists to avoid exactly this.
Sorting in place when you need original indices. The sort-based solution requires carrying the original indices along; a naive sorted call without the index loses the information the problem is asking for.

Interview follow-ups to expect

What if the array is sorted? → Use two pointers, O(1) extra space.
What if multiple valid pairs exist and you need all of them? → Hash map of value → list of indices; on each match, emit one pair per previous occurrence.
Three Sum: find triplets that sum to zero. → Sort the array; fix one element and do converging two-pointer on the rest. O(n²).
Four Sum or K-Sum. → Recurse on k; base case is the 2-sum two-pointer. O(n^(k-1)).

Two Sum

Problem walkthrough: statement, hints, solution, mistakes