Two Sum

Given a list of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.

Examples

Input:  nums = [2,7,11,15], target = 9
Output: [0,1]        # nums[0] + nums[1] == 9

Input:  nums = [3,2,4], target = 6
Output: [1,2]

Constraints

• 2 <= len(nums) <= 10^4
• Exactly one valid answer exists.

Approach — complement lookup with a hash map

Brute force checks every pair: O(n^2). The trick is to reframe the question. As you scan, for the current number x you're really asking: "have I already seen target - x?" A hash map gives that answer in O(1).

Store each number's index as you go. Before storing x, check whether its complement is already in the map — if so, you've found the pair.

Solution

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}          # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []                          # unreachable given the guarantee

Explanation

• One pass suffices. We check the complement before inserting the current number, so we never pair an element with itself, and we only ever need numbers to our left.
• Why a dict, not a set? We must return indices, so we map value → index.
• Duplicates are fine: if nums = [3,3], the first 3 is stored, and when the second 3 arrives its complement 3 is already present.

Complexity

• Time: O(n) — one pass, O(1) map operations.
• Space: O(n) — up to n entries in the map.

Interview tips

This is the canonical "brute force → hash map" optimization. Say the complement insight out loud; interviewers are listening for why the map turns O(n^2) into O(n).