Two Sum — Solution

Problem

Given an array 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.

Example:

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

Intuition

The brute force approach checks every pair of numbers, but we can do much better. The key insight is: for each number nums[i], we need to know if target - nums[i] exists elsewhere in the array. A hash map lets us answer that question in O(1).

Approach 1 — Brute Force

Check every pair (i, j) where i < j. If they sum to target, return the indices.

Steps:

1. For each index i, scan every index j to the right of it
2. If nums[i] + nums[j] == target, return [i, j]

1def twoSum(nums, target):
2    for i in range(len(nums)):
3        for j in range(i + 1, len(nums)):
4            if nums[i] + nums[j] == target:
5                return [i, j]

• Time: O(n²) — two nested loops over n elements
• Space: O(1)

Approach 2 — Hash Map (Optimal)

Do a single pass. For each number, check if its complement (target - num) is already in a hash map. If yes, we're done. If no, store the current number and its index.

Steps:

1. Create an empty hash map (value → index)
2. For each number, compute complement = target - num
3. If complement is in the map, return [map[complement], current_index]
4. Otherwise, store num → current_index in the map

1def twoSum(nums, target):
2    seen = {}  # maps value -> index
3    for i, num in enumerate(nums):
4        complement = target - num
5        if complement in seen:
6            # complement was stored in a previous iteration, so indices are distinct
7            return [seen[complement], i]
8        seen[num] = i

• Time: O(n) — single pass, each hash map lookup is O(1)
• Space: O(n) — hash map stores up to n entries

Complexity Summary

Common Mistakes

• Using the same element twice: The hash map approach avoids this naturally — we only look up values stored in previous iterations, so index i is never in the map when we check for its complement.
• Returning values instead of indices: The problem asks for indices, not the numbers themselves.
• Storing before checking: If you seen[num] = i before checking for the complement, a number could match itself (e.g., target = 6, num = 3 would find index of 3 in the map immediately). Always check first, then store.

Related Problems

• 3sum — extends two-sum to three numbers; sort + two pointers
• two-sum-ii-input-array-is-sorted — sorted input allows two-pointer instead of hash map
• 4sum — two nested loops reduce it to two-sum
• contains-duplicate — same hash set pattern
• top-k-frequent-elements — hash map for counting frequencies