Two Sum

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

Source: https://leetcode.com/problems/two-sum/

Difficulty: Easy

Topics: Array, Hash Map

Problem Statement

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. You can return the answer in any order.

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

Examples

Example 1:

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

Example 2:

1Input:  nums = [3, 2, 4], target = 6
2Output: [1, 2]
3Reason: nums[1] + nums[2] = 2 + 4 = 6

Example 3:

1Input:  nums = [3, 3], target = 6
2Output: [0, 1]
3Reason: nums[0] + nums[1] = 3 + 3 = 6

Core Concept: The Complement

Before diving into approaches, understand this key idea:

For any element nums[i], the value we need to pair it with is called its complement:

1complement = target - nums[i]

If the complement exists at a different index j in the array, then [i, j] is the answer.

Every approach below is just a different strategy for finding the complement efficiently.

Approach 1: Brute Force

Theory

Check every possible pair of elements in the array. For each pair (i, j), check if their sum equals the target. Since we are checking all pairs, we are guaranteed to find the answer. This approach requires no extra memory but is slow for large inputs.

Explanation

1
Start with the first element at index i = 0.
2
For each element at index i, loop through every element at index j where j > i.
3
Check if nums[i] + nums[j] == target.
4
If yes, return [i, j] immediately.
5
If the inner loop finishes without finding a pair, move i forward by one and repeat.
6
The problem guarantees exactly one solution, so we will always find a pair before the loops end.

The reason we start j from i + 1 and not from 0 is to avoid:

Using the same element twice (e.g., pairing index 0 with itself).
Checking duplicate pairs (e.g., pair (0,1) and pair (1,0) are the same).

Example

1nums = [2, 7, 11, 15], target = 9
2
3Step 1: i = 0, nums[i] = 2
4    j = 1, nums[j] = 7  -->  2 + 7 = 9  == target  -->  Return [0, 1]

1nums = [3, 2, 4], target = 6
2
3Step 1: i = 0, nums[i] = 3
4    j = 1, nums[j] = 2  -->  3 + 2 = 5  != 6
5    j = 2, nums[j] = 4  -->  3 + 4 = 7  != 6
6
7Step 2: i = 1, nums[i] = 2
8    j = 2, nums[j] = 4  -->  2 + 4 = 6  == target  -->  Return [1, 2]

Implementation

1# Python
2
3class Solution:
4    def twoSum(self, nums: list[int], target: int) -> list[int]:
5        n = len(nums)
6
7        for i in range(n):
8            for j in range(i + 1, n):
9                if nums[i] + nums[j] == target:
10                    return [i, j]
11
12        return []  # This line is never reached; problem guarantees one solution

Complexity Analysis

Time Complexity: O(n^2)

We have two nested loops. For an array of size n, the outer loop runs n times and the inner loop runs up to n - 1 times. In the worst case, the answer is the last pair we check, giving us approximately n * (n-1) / 2 checks, which is O(n^2).

Space Complexity: O(1)

We only use a fixed number of integer variables (i, j). We do not use any extra data structure that grows with the input size.

Approach 2: Two-Pass Hash Map

Theory

Instead of checking every pair, we use a hash map to look up any number in O(1) time. In the first pass, we record every number and its index into the map. In the second pass, for each number we check if its complement already exists in the map. This reduces the time complexity from O(n^2) to O(n).

Explanation

Why a hash map?

A hash map allows us to answer the question "does value X exist in the array, and if so, at what index?" in O(1) average time, rather than scanning the array each time in O(n) time.

Step-by-step:

1
Create an empty hash map called num_map that stores value -> index.
2
First pass - Build the map:

Iterate through the entire array and insert each element as num_map[nums[i]] = i. After this pass, every value in the array is in the map.

1
Second pass - Find the complement:

Iterate through the array again. For each index i:

- Compute complement = target - nums[i].

- Check if complement exists in the map.

- If it exists, also verify that num_map[complement] != i. This guard is important because we cannot use the same element twice. For example, if nums = [3, 5] and target = 6, when i = 0 the complement is 3, which exists in the map at index 0 itself. We must skip this.

- If the complement exists at a different index, return [i, num_map[complement]].

Example

1nums = [2, 7, 11, 15], target = 9
2
3--- Pass 1: Build the map ---
4
5i = 0, nums[0] = 2   -->  map = {2: 0}
6i = 1, nums[1] = 7   -->  map = {2: 0, 7: 1}
7i = 2, nums[2] = 11  -->  map = {2: 0, 7: 1, 11: 2}
8i = 3, nums[3] = 15  -->  map = {2: 0, 7: 1, 11: 2, 15: 3}
9
10--- Pass 2: Find the complement ---
11
12i = 0, nums[0] = 2,  complement = 9 - 2 = 7
13       Is 7 in map?  Yes, at index 1
14       Is map[7] != 0?  Yes (1 != 0)
15       Return [0, 1]

1nums = [3, 3], target = 6  (shows why we need the index guard)
2
3--- Pass 1: Build the map ---
4
5i = 0, nums[0] = 3   -->  map = {3: 0}
6i = 1, nums[1] = 3   -->  map = {3: 1}   <-- index 1 overwrites index 0 for key 3
7
8--- Pass 2: Find the complement ---
9
10i = 0, nums[0] = 3,  complement = 6 - 3 = 3
11       Is 3 in map?  Yes, at index 1
12       Is map[3] != 0?  Yes (1 != 0)
13       Return [0, 1]

Note: When both elements have the same value (like [3, 3]), the first pass stores only the last index for that value. This is actually fine because when we check i = 0, the map has 3 -> 1, which is a different index, so it passes the guard and we return correctly.

Implementation

1# Python
2
3class Solution:
4    def twoSum(self, nums: list[int], target: int) -> list[int]:
5        num_map = {}
6
7        # Pass 1: build the map
8        for i in range(len(nums)):
9            num_map[nums[i]] = i
10
11        # Pass 2: find the complement
12        for i in range(len(nums)):
13            complement = target - nums[i]
14            if complement in num_map and num_map[complement] != i:
15                return [i, num_map[complement]]
16
17        return []

Complexity Analysis

Time Complexity: O(n)

We make two separate passes over the array, each taking O(n) time. Hash map insertions and lookups are O(1) on average. So total time is O(n) + O(n) = O(n).

Space Complexity: O(n)

The hash map stores at most n entries (one for each element in the array). In the worst case (no match found until the very last pair), all n elements are stored.

Approach 3: One-Pass Hash Map (Optimal)

Theory

We can do even better than two passes. Instead of first building the entire map and then searching it, we do both in a single loop. As we iterate through the array, we check if the current element's complement was already seen earlier. If it was, we return the answer immediately. If not, we add the current element to the map and continue. This way, we only ever look back at elements we have already processed, which naturally prevents using the same element twice.

Explanation

Why does one pass work?

Think about it this way: if two elements at indices i and j (where i < j) form the answer, then when we reach index j, index i has already been inserted into the map. So looking up target - nums[j] will find it. We never need to look ahead, only backward.

Step-by-step:

1
Create an empty hash map num_map that stores value -> index.
2
Iterate through the array. For each index i:

- Compute complement = target - nums[i].

- Check if complement is already in the map.

- If yes, the complement was seen at some earlier index. Return [num_map[complement], i].

- If no, insert nums[i] into the map as num_map[nums[i]] = i and move on.

1
There is no need for the extra same-index guard that Approach 2 needed, because we only look up elements that were inserted in previous iterations (i.e., at strictly smaller indices). So we can never accidentally match an element with itself.

Dry Run

Example 1:

1nums = [2, 7, 11, 15], target = 9
2
3i = 0:  num = 2,  complement = 9 - 2 = 7
4        Is 7 in map {}?  No
5        Insert 2 --> map = {2: 0}
6
7i = 1:  num = 7,  complement = 9 - 7 = 2
8        Is 2 in map {2: 0}?  Yes, at index 0
9        Return [0, 1]

Example 2:

1nums = [3, 2, 4], target = 6
2
3i = 0:  num = 3,  complement = 6 - 3 = 3
4        Is 3 in map {}?  No
5        Insert 3 --> map = {3: 0}
6
7i = 1:  num = 2,  complement = 6 - 2 = 4
8        Is 4 in map {3: 0}?  No
9        Insert 2 --> map = {3: 0, 2: 1}
10
11i = 2:  num = 4,  complement = 6 - 4 = 2
12        Is 2 in map {3: 0, 2: 1}?  Yes, at index 1
13        Return [1, 2]

Example 3 (duplicate values):

1nums = [3, 3], target = 6
2
3i = 0:  num = 3,  complement = 6 - 3 = 3
4        Is 3 in map {}?  No
5        Insert 3 --> map = {3: 0}
6
7i = 1:  num = 3,  complement = 6 - 3 = 3
8        Is 3 in map {3: 0}?  Yes, at index 0
9        Return [0, 1]

Notice that in Example 3, when i = 1, the map contains {3: 0} from the previous step. The complement 3 is found at index 0, which is a different index from i = 1. Correct answer returned without any special guard needed.

Implementation

1# Python
2
3class Solution:
4    def twoSum(self, nums: list[int], target: int) -> list[int]:
5        num_map = {}  # stores value -> index
6
7        for i, num in enumerate(nums):
8            complement = target - num
9
10            if complement in num_map:
11                return [num_map[complement], i]
12
13            num_map[num] = i
14
15        return []  # This line is never reached

Complexity Analysis

Time Complexity: O(n)

We make exactly one pass through the array. Each iteration does a constant amount of work: one subtraction, one hash map lookup (O(1) average), and at most one hash map insertion (O(1) average). So overall time is O(n).

Space Complexity: O(n)

In the worst case (when the answer pair is the last two elements we check), we insert all n - 1 elements into the map before finding the answer. So the map holds up to O(n) entries.

Comparison of All Approaches

Approach	Time Complexity	Space Complexity	Passes	Notes
Brute Force	O(n^2)	O(1)	1 (nested)	Too slow for large inputs
Two-Pass Hash Map	O(n)	O(n)	2	Needs an index guard
One-Pass Hash Map	O(n)	O(n)	1	Best: clean, fast, no guard needed

Key Takeaways

1. The complement idea is central.

Instead of asking "do any two numbers sum to target?", rephrase it as "for this number, does its complement exist somewhere else?" This mental shift leads directly to the hash map solution.

2. Hash map enables O(1) lookup.

The reason we go from O(n^2) to O(n) is that a hash map answers "is this value present?" in O(1) instead of O(n) (like a linear scan would).

3. One-pass is cleaner than two-pass.

In two-pass, you have to add a guard to make sure you are not pairing an element with itself. In one-pass, this problem disappears naturally because you only look at previously inserted elements, which are always at strictly smaller indices.

4. Always prefer One-Pass Hash Map in interviews.

It is the most optimal, concise, and correct solution. When asked to improve on brute force, go directly to one-pass hash map and explain the complement concept.