Two Sum#

Given an array of integers and a target value, find the indices of the two numbers that add up to the target. Each input has exactly one solution, and you cannot reuse the same element twice. Return the pair of indices in any order.

Example#

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

Brute force#

Check every pair of indices with two nested loops and return the first pair that sums to the target. This is simple but slow.

• Time: O(n^2), one pass for each element.
• Space: O(1).

Optimal approach#

Walk through the array once and keep a hash map from each value you have seen to its index. For the current number, compute the complement (target - num). If the complement is already in the map, you have found the answer. Otherwise, store the current number and move on. Because dictionary lookups are average O(1), a single pass is enough.

Python solution#

1def two_sum(nums, target):
2    seen = {}
3    for i, num in enumerate(nums):
4        complement = target - num
5        if complement in seen:
6            return [seen[complement], i]
7        seen[num] = i
8    return []

Complexity#

• Time: O(n), one pass with constant-time lookups.
• Space: O(n) for the hash map in the worst case.

This problem is the canonical example of the hashing pattern. To see how it fits into a full study plan, follow the 60-day challenge.