Two Sum

Overview

The goal is to find two distinct indices in an array such that the values at those indices sum to a specific target. Since the problem guarantees exactly one solution and prohibits using the same element twice, we are looking for a unique pair $(a, b)$ such that $a + b = \text{target}$.

The core intuition relies on the relationship: complement = target - current_value. If we know the value we are looking for (the complement), we just need an efficient way to check if it exists elsewhere in the array.

Brute Force

The most straightforward approach is to check every possible pair of numbers in the array. We use two nested loops: the outer loop picks the first element, and the inner loop iterates through the remaining elements to see if their sum equals the target.

def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]

• Time complexity: O(n²) — We use nested loops to compare every possible pair, resulting in quadratic time.
• Space complexity: O(1) — We only use a constant amount of extra space for loop variables.

Optimal / Best Approach

We can improve the time complexity significantly by using a Hash Map (Python dictionary). As we iterate through the array, we calculate the complement needed to reach the target. Instead of searching the rest of the array for this complement, we look it up in our dictionary.

1. Create an empty dictionary prev_map to store value: index.
2. Iterate through nums using both index i and value n.
3. Calculate diff = target - n.
4. If diff exists in prev_map, we found our pair. Return [prev_map[diff], i].
5. If not, add the current value and its index to prev_map and continue.

def two_sum(nums: list[int], target: int) -> list[int]:
    # Map to store value -> index
    prev_map = {} 
    
    for i, n in enumerate(nums):
        diff = target - n
        if diff in prev_map:
            return [prev_map[diff], i]
        prev_map[n] = i

• Time complexity: O(n) — We traverse the list containing $n$ elements exactly once. Each lookup in the hash map takes $O(1)$ on average.
• Space complexity: O(n) — In the worst case, we may need to store all $n$ elements in the hash map before finding the complement.

Why This Works

By using a hash map, we trade space for speed.

In the brute force approach, "searching" for the complement takes $O(n)$ time. By storing visited elements in a hash map, "searching" for the complement becomes an $O(1)$ operation. Note that we populate the map as we go; this naturally prevents us from using the same element twice (the current element isn't in the map yet when we check for its complement).