Two sum: indices of the pair that adds up to a target

Given an integer array nums and a target, return the indices of the two different elements whose values add up to target. Exactly one such pair exists. Solve it with a hash map, then without one, and compare the costs.

Interface

Unless you agree on a different interface with the interviewer, assume:

• two_sum(nums: list[int], target: int) -> list[int] — [i, j] with i < j and nums[i] + nums[j] == target. An element can't pair with itself, but equal values at different indices can.

Example

two_sum([2, 7, 11, 15], 9)  ->  [0, 1]
two_sum([3, 2, 4], 6)       ->  [1, 2]   # index 0 can't be used twice for 3 + 3
two_sum([3, 3], 6)          ->  [0, 1]

Constraints

• 2 <= len(nums) <= 10,000; values and target in [-10^9, 10^9].
• Exactly one valid pair exists.

Clarifying questions

• Is there always exactly one answer? What if there were none or several?
• Can an element pair with itself?
• In what order should the indices come back?
• Is the array sorted?

What a strong answer covers

• The O(n^2) brute force as a baseline.
• One pass with a hash map from value to index: for each nums[j], look up target - nums[j] among earlier values before inserting nums[j], which handles [3, 3] correctly. O(n) time and space.
• Without a hash map: sort the indices by value, then walk two pointers from both ends. O(n log n) time, O(n) for the index array, and the need to map back to original indices.
• When each is preferable (memory, already sorted input, many queries on the same array).
• Tests: negative numbers, duplicates, the pair at the ends.

Follow-ups

• Return all pairs of values that sum to the target, without duplicates.
• The array is sorted: do it in O(1) extra space.
• Three numbers that sum to the target.
• A stream of numbers with add(x) and find(target) calls.