How do you solve Two Sum in an interview?

Short answer: Use a hash map from value → index while scanning once. For each number x, check if target − x is already seen; if yes, return both indices. This is O(n) time and O(n) space — the expected answer after you briefly mention the O(n²) nested-loop brute force.

Problem statement

Given an array of integers and a target, return indices of two numbers that add up to the target. Assume exactly one solution and you may not use the same element twice.

Interview approach

1. Clarify constraints: duplicates allowed? multiple answers? need indices or values?
2. State brute force: check every pair in O(n²).
3. Propose hash map: while iterating i, look up target − nums[i].
4. Store nums[i] → i after the lookup (avoid using the same index).
5. Walk through a small example out loud.
6. State time/space and discuss follow-ups (sorted array → two pointers).

Brute force (mention first)

Nested loops comparing every pair — correct but too slow for large n.

Optimal idea

One pass with Dictionary/HashMap. Lookup is average O(1).

Sample solution

// C#
int[] TwoSum(int[] nums, int target) {
    var map = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++) {
        int need = target - nums[i];
        if (map.TryGetValue(need, out int j)) return new[] { j, i };
        map[nums[i]] = i;
    }
    throw new InvalidOperationException("No solution");
}

Complexity

Time O(n), Space O(n).

Edge cases to mention

• Negative numbers
• Duplicates (e.g. [3,3], target 6)
• Empty or single-element array (no solution)

Common follow-ups

• What if the array is sorted?
• Return all unique pairs instead of indices
• Three Sum

Mistakes to avoid

• Adding to the map before checking (can reuse same index)
• Forgetting to discuss complexity

Always start with brute force, then optimize — interviewers score communication as much as code.