Two Sum – Solution & Complexity

Q: What is the time and space complexity of Two Sum?

The optimal Two Sum solution runs in `O(n)` time and `O(n)` space. Store each value's index in a hash map and check for the complement (target - num) as you scan.

Q: What is the most efficient way to solve Two Sum?

Store each value's index in a hash map and check for the complement (target - num) as you scan. This gives `O(n)` time complexity, and is a classic arrays and hashmap problem.

Q: How do you solve Two Sum in Python, JavaScript, Java, Go & Rust?

We provide a worked Two Sum solution in Python, JavaScript, Java, Go & Rust with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Two Sum an easy or hard interview question?

Two Sum is generally rated **Easy**. It tests arrays and hashmap, which are common coding-interview patterns.

Solution Walkthrough

1. Understanding the Problem

You are given an array of integers and a target sum.
The task is to find two distinct numbers in the array that add up to the target.
You should return their indices as a result.

2. Brute Force Approach (Inefficient)

Start by considering a brute force approach where you check every possible pair.
For each number, iterate through the remaining numbers and check if they add up to the target.
This approach has O(n²) time complexity.

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

3. Identifying the Core Operation

The core operation is checking whether two numbers in the array add up to the target.
For each number num, check if there’s another number complement such that: num + complement = target
The complement can be calculated as complement = target - num.

4. Using a Hash Map for Efficient Lookup

Searching through the array takes O(n) time if done linearly. To make this faster, you can use a hash map (dictionary).
A hash map allows for constant-time lookups (O(1)), so you can check if the complement exists as you iterate through the array.

5. Initializing the Hash Map

Create an empty hash map to store numbers and their indices as you iterate through the array.

def two_sum(nums, target):
    hash_map = {}  # Initialize an empty dictionary
    return hash_map

6. Iterate Through the Array and Calculate Complement

Loop through the array.
For each number, calculate its complement (the difference between the target and the current number).
The complement is calculated as target - num.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num  # Calculate the complement
    return None

7. Check if the Complement Exists in the Hash Map

For each number, check if the complement exists in the hash map.
If the complement is already in the hash map, it means you’ve found two numbers that add up to the target.
Return the indices of the current number and its complement.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:  # Check if complement exists
            return [hash_map[complement], i]  # Return the indices
    return None

8. Store the Current Number in the Hash Map

If the complement is not found in the hash map, store the current number and its index in the hash map.
This ensures that it can be checked as a complement for future numbers.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i  # Store current number
    return None

9. Dry run / state trace

Trace nums = [3, 2, 4], target = 6. Store only numbers that appear before the current index.

i	num	needed complement	map before check	action
0	3	3	`{}`	`3` is not present; store `{3: 0}`
1	2	4	`{3: 0}`	`4` is not present; store `{3: 0, 2: 1}`
2	4	2	`{3: 0, 2: 1}`	`2` is present at index `1`; return `[1, 2]`

The invariant prevents using the same element twice because the current 4 is checked before it is inserted.

10. Common mistakes & interviewer follow-ups

Returning the two values instead of their indices; the judge expects positions.
Inserting the current value before checking its complement, which can reuse the same element when target = 2 * num.
Assuming the input is sorted and using two pointers without preserving original indices.
Overwriting duplicate values too early in a two-pass map; the one-pass version avoids this by checking first.
Follow-ups: how would you return all pairs, handle no guaranteed solution, or reduce memory if the array were sorted?

Recommended next problem in this pattern: Valid Anagram, which uses a hash map for frequency balance instead of complement lookup.

11. Handle Edge Cases

Ensure that the input array has at least two numbers.
Return None if no solution is found.

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return None  # Return None if no solution is found

Learn the Arrays & Hashing pattern: recognition cues, invariant, and ordered practice →