#1 Two Sum

EasyArrays & Hashing~15 min

You're given an array of integers nums and a target integer target. Exactly one pair of positions in the array holds values that add up to target, find that pair and return the two indices (in any order).

You may not use the same element twice, and you can assume exactly one valid answer exists.

Examples

Inputnums = [2, 7, 11, 15], target = 9

Output[0, 1]

nums[0] + nums[1] = 2 + 7 = 9, so the answer is [0, 1].

Inputnums = [3, 2, 4], target = 6

Output[1, 2]

3 + 3 would use the first element twice. The valid pair is 2 + 4.

Constraints

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Exactly one valid answer exists

Hints

Intuition

Every hard problem in this track is some disguise of the question this problem asks openly: can you trade memory for time?

Walk the array. At element x, the pair you're looking for is complete only if its other half, target − x, has already walked past you. The brute force re-scans the whole array to check that, O(n) work per element, O(n²) total. But "have I seen this value before, and where?" is exactly what a hash map answers in constant time. Carry one with you, and each element needs only one lookup and one insert.

The array doesn't get faster, your memory of it does.

Approaches

1. Brute force, check every pair

O(n²) time · O(1) space

Two nested loops: for each i, scan every j > i and test nums[i] + nums[j] === target. It's correct, it uses no extra memory, and it's the right first thing to say in an interview, it proves you understand the problem and gives you a baseline to beat. At 10⁴ elements that's ~5 × 10⁷ pair checks: fine once, painful as a building block.

2. One-pass hash map

O(n) time · O(n) space

Keep a map from value → index of the elements seen so far. For each element x at index i:

Compute the complement c = target − x.
If c is already in the map, you're done: return [map[c], i].
Otherwise record map[x] = i and keep walking.

Checking before inserting is the subtle part, it guarantees the two indices are distinct, so target = 6 with nums = [3, 2, 4] can never match 3 with itself. Duplicates also fall out naturally: with [3, 3] and target 6, the second 3 finds the first one in the map.

Solution

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index of elements we've walked past
    for i, x in enumerate(nums):
        c = target - x
        if c in seen:          # complement already behind us: pair complete
            return [seen[c], i]
        seen[x] = i            # record AFTER the check, never match self
    return []  # unreachable per constraints: exactly one answer exists

Common pitfalls

Inserting into the map before checking the complement, with `target = 6` and a `3` in the array, the element happily pairs with itself.
Returning values instead of indices. The problem asks *where*, not *what*.
Sorting first to use two pointers, sorting destroys the original indices, which are the answer. (Two pointers is the right tool for Two Sum II, where the array arrives pre-sorted.)

Going further

Two Sum II (sorted input): the two-pointer solution uses O(1) space, why does sorting make the memory trade unnecessary?
3Sum: fix one element, then this problem is the subproblem. Most k-sum problems reduce this way.
What if the array is huge but the values fit in a small range? A counting array can replace the hash map.