*Two Sum* is a rather famous coding interview problem, often asked in Python coding interviews. Being problem #1 on LeetCode, you may also know it as the *LeetCode Two Sum.*

The problem is stated as follows:

Given an array of integers`A = [a1, a2, ...]`

and an integer`S`

, write a function`two_sum(A,S)`

that returns all pairs of indices`(i, j), i≠j`

such that`A[i] + A[j] == S`

.

If there are no such pairs, return an empty array`[]`

.

In other words, we want to find all pairs of integers from `A`

that add up to `S`

and return their positions in the array.

Here are a few examples:

```
two_sum(A=[5, 7, 2], S=9) -> [(1, 2)] # A[1] + A[2] == 9
two_sum(A=[3, 5, 7, 9], S=12) -> [(0, 3), (1, 2)]
two_sum(A=[3, 23, 19], S=21) -> [] # There is no such pair
two_sum(A=[1], S=10) -> [] # Only one integer, no valid pairs
```

Seems easy, so what's the catch? We'll there's a better solution than the naive one. Let's go step by step.

## Naive Solution - Two Nested Loops, O(n²)

Let's consider the following solution: for each distinct pair of indices `(i,j)`

check if `A[i] + A[j] == S`

. If true, add the pair to the results.

```
def two_sum(A, S):
pairs = []
for i in range(len(A)):
for j in range(i+1, len(A)):
if A[i] + A[j] == S:
pairs.append((i, j))
return pairs
```

It wouldn't be such a well known problem if this was the desired solution, right?

The time complexity of this solution is O(n²). In fact, we'll have exactly $$\sum_{n=1}^{len(A)-1}n=\frac{\left(len(A)-1\right)\cdot\left(1+len(A)-1\right)}{2}=\frac{\left(len(A)-1\right)\cdot len(A)}{2}$$ iterations of the inner loop. Here $len(A)$ denotes the number of elements in our input array `A`

.

This means that for an input array with 20,000 integers we'll check 1.999.900.000 pairs. This takes ~20 seconds on an intel i7 machine.

## Using a Hash Map - O(n)

Let's analyze our solution closely.

We have 2 nested loops. The outer loop considers each integer in the array, `A[i]`

. The inner loop then searches for the complement, `A[j]`

such that `A[i] + A[j] == S`

.

Do you see the catch? For each `A[i]`

we know exactly what number we're looking for - it's the complement `C`

, such that `C == S - A[i]`

.

Here's the trick: If we already knew all the positions of the complement in `A`

we could just add the pairs of indices to the result and move to the next `i`

.

So, let's do exactly that with a hash map, which is nothing other than `dict`

in Python. We'll first construct a `dict`

which for each integer `x`

from `A`

holds an array of indices where `x`

occurs.

For example, for the following array `A`

:

`[2, 6, 10, 3, 7, 5, 9, 6, 6, 1]`

We want to build the following dictionary:

```
{
1: [9],
2: [0],
3: [3],
5: [5],
6: [1, 7, 8 ],
7: [4],
9: [6],
10: [2]
}
```

Once we have it, it takes O(1) time to find out that `6 occurs in A at indices [1, 7, 8]`

, `9 occurs at index [6]`

, and so on.

The following function builds this dictionary for us:

```
def build_index_dict(A):
indices = {}
for i in range(len(A)):
a = A[i]
if a not in indices:
indices[a] = []
indices[a].append(i)
return indices
```

Now let's use this lookup dict to speed up our initial solution:

```
def build_index_dict(A):
indices = {}
for i in range(len(A)):
a = A[i]
if a not in indices:
indices[a] = []
indices[a].append(i)
return indices
def two_sum(A, S):
index_dict = build_index_dict(A)
pairs = []
for i in range(len(A)):
C = S - A[i] # C <- complement of A[i] to S
if C in index_dict:
for j in index_dict[C]: # run through all indices of C
if j > i: # make sure we're not repeating any pairs
pairs.append((i, j))
return pairs
```

Now, you may argue that this is still an O(n²) solution. You'd be right.

To see why this is still O(n²), consider the following input `([1, 1, 1, 1, 1, 1], 2)`

. However, it's not hard to see that our hash map solution will be at least as good as the naive solution, for any input.

Now consider a slightly altered problem formulation - *assume that all integers in A[i] are unique*. In that case, we can change the solution as follows:

- Indices dict won't need to hold an array of indices. For each integer there is only one position in
`A`

where it occurs. - For each
`A[i]`

the complement either exists at a single position, or it doesn't exist at all. The inner loop is not really a loop anymore.

```
def build_index_dict(A):
indices = {}
for i in range(len(A)):
a = A[i]
indices[a] = i
return indices
def two_sum(A, S):
index_dict = build_index_dict(A)
pairs = []
for i in range(len(A)):
C = S - A[i]
if C in index_dict:
j = index_dict[C]
if j > i:
pairs.append((i, j))
return pairs
```

This makes our solution run in O(n) time: we build `index_dict`

in O(n) and find all pairs of indices in O(n).