Two Sum Problem

Given an array of integers and a target value, the Two Sum problem asks you to find the indices of two numbers such that they add up to the target.

Brute Force Approach

Check every pair of elements using nested loops and test if they sum to the target. This works but takes O(n²) time.

Optimal Approach — Hash Map

Traverse the array once. For each element, calculate the complement (target - element) and check if it already exists in a hash map of previously seen values. If found, return the pair of indices; otherwise, store the current element and its index.

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1]

Complexity

Variations

• Two Sum on a sorted array — solved with the two-pointer technique in O(n) time and O(1) space.
• Three Sum / Four Sum — extensions that build on the same hashing or two-pointer ideas.