Two Sum Solution Explained – Step-by-Step

Data Structures / Array

Two Sum

Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have 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: Because nums[0] + nums[1] == 9, we return [0, 1].

Explanation

The most efficient approach to solve this problem is using a hash map (dictionary). The key insight is that for each number in the array, we can check if its complement (target - current number) has already been seen.

We iterate through the array once, and for each element:

Calculate the complement = target - nums[i]
Check if the complement exists in our hash map
If yes, return the current index and the complement's index
If no, store the current number and its index in the hash map

This approach works because we only need to find one pair that sums to the target. By the time we check a number, all previous numbers have been stored in the hash map.

Idea Map

Start

Create empty hash_map = {}

For each num in nums

1. complement = target - num
2. If complement in hash_map
Return [hash_map[complement], i]
3. Else: hash_map[num] = i

End

Complexity Analysis

Time Complexity

O(n) - We traverse the array once, and each hash map lookup is O(1) on average.

Space Complexity

O(n) - In the worst case, we store all n elements in the hash map.

Code


def twoSum(nums, target):
Initializes the function `twoSum` which takes the array `nums` and the `target` sum as input.
    hash_map = {}
Creates an empty dictionary to store numbers and their indices for O(1) lookups.
    for i, num in enumerate(nums):
Loops through the array with both index `i` and value `num` using `enumerate()`.
        complement = target - num
Calculates the value needed to add to `num` to reach the `target`.
        if complement in hash_map:
Checks if the required complement has been seen before (exists in our hash map).
            return [hash_map[complement], i]
If complement exists, return its index and current index - we found the pair!
        hash_map[num] = i
If complement not found, store current number with its index for future lookups.
    return []
Return empty list if no solution found (shouldn't happen per problem constraints).


public int[] twoSum(int[] nums, int target) {
Initializes the function `twoSum` which takes the array `nums` and the `target` sum as input.
    Map<Integer, Integer> map = new HashMap<>();
Creates a HashMap to store numbers as keys and their indices as values for O(1) lookups.
    for (int i = 0; i < nums.length; i++) {
Loops through the array with index `i` from 0 to the end of the array.
        int complement = target - nums[i];
Calculates the value needed to add to `nums[i]` to reach the `target`.
        if (map.containsKey(complement)) {
Checks if the required complement exists as a key in our HashMap.
            return new int[] { map.get(complement), i };
If complement exists, return its index and current index - we found the pair!
        }
End of the if statement.
        map.put(nums[i], i);
If complement not found, store current number with its index for future lookups.
    }
End of the for loop.
    return new int[] {};
Return empty array if no solution found (shouldn't happen per problem constraints).
}
End of the function.


vector<int> twoSum(vector<int>& nums, int target) {
Initializes the function `twoSum` which takes a reference to the vector `nums` and the `target` sum as input.
    unordered_map<int, int> map;
Creates an unordered_map (hash map) to store numbers as keys and their indices as values for O(1) lookups.
    for (int i = 0; i < nums.size(); i++) {
Loops through the vector with index `i` from 0 to the end of the vector.
        int complement = target - nums[i];
Calculates the value needed to add to `nums[i]` to reach the `target`.
        if (map.find(complement) != map.end()) {
Checks if the required complement exists in our unordered_map (find doesn't return end()).
            return { map[complement], i };
If complement exists, return its index and current index - we found the pair!
        }
End of the if statement.
        map[nums[i]] = i;
If complement not found, store current number with its index for future lookups.
    }
End of the for loop.
    return {};
Return empty vector if no solution found (shouldn't happen per problem constraints).
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Using the same element twice

Always add the current element to the hash map after checking for the complement. If you add it first, you might match an element with itself.

💡

Multiple valid pairs

The problem guarantees exactly one solution, so you can return as soon as you find the first valid pair.

✓

Negative numbers and zero

The hash map approach handles negative numbers and zero correctly without any special cases.

What is a Hash Map?

A hash map (or hash table) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Learn more about hash tables →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Two Sum' problem on LeetCode.

AlgoExplained.dev