Two Sum

Problem

Given an array of integers nums and an integer target, return the 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. Return the answer in any order.

Example: nums = [2, 7, 11, 15], target = 9 → [0, 1].

What the interviewer is testing

• Can you spot the space-for-time tradeoff (hash map)?
• Do you enumerate edge cases without prompting (empty array, no solution, duplicates)?
• Do you state complexity out loud before writing code?

Brute-force solution — O(n²) time, O(1) space

The literal reading: try every pair. Correct but the interviewer's follow-up is always "can you do better than O(n²)?"

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

Optimal solution — O(n) time, O(n) space

As we scan, remember every value we've seen and the index we saw it at. For each new value x, check whether target - x is already in the map — if so, we have our pair.

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
    return []

Complexity — what to say out loud

"Time is O(n) — one pass through the array. Space is O(n) — the hash map can hold up to n entries in the worst case. It's the standard space-for-time tradeoff."

Edge cases the interviewer will ask about

• No valid pair — return an empty list (or per the prompt, throw).
• Duplicate values, target is 2×value — e.g. [3, 3], target 6. Handled naturally because we check the map before inserting the current element.
• Negative numbers or zero — no special handling needed.
• Very large array with a solution near the start — early return, still O(n) worst case.

Common follow-ups

• "What if the array is sorted?" — Use two pointers from both ends, get O(n) time and O(1) space.
• "What if we want all pairs, not just one?" — Continue past the first hit, collect matches. Still O(n) time.
• "What about 3Sum?" — Sort, then for each element run the two-pointer sum-to-target on the remaining array. That's a separate problem.

How to verbalize your answer

"This looks like a hash-map problem — we want O(1) lookup for the complement. I'll scan once, and for each value check whether target - value is already in a map keyed by value with index as the value. If yes, return the two indices. If no, add the current value to the map and keep going. Time O(n), space O(n)."

State the approach before you type. That's the difference between passing on communication and getting a "could you have arrived at this faster?" note in the feedback.