Day - 1 of the series - The challenge is a *2-sum problem* that goes like this:

You have an *array*. Find *2 values* such that their sum equals a *target value*

Having solved it earlier I quickly jumped to solve it as below

```
lines = file('input-1.txt', 'r')
arr = []
index = 0
for line in lines:
val = int(line)
for entry in arr:
if val + entry == 2020:
print("Result: " + str(val * entry))
arr.append(val)
```

However, my friend Ram challenged that it could be solved with O(n) complexity itself. As he hints *HashMaps* so I try

By leveraging HashMaps, we further adhere to our core principles - *Never process anything that was already seen once*.

```
from collections import defaultdict
"""
We make up our 'arr' a HashMap - i.e a dictionary in Python.
Since a lookup in Hashmap is in constant time, we can avoid one loop.
Keys would be the values we read in.
We don't care for values. Let them default to zero
If we find the difference of (2020 and incoming value) as an existing key, simply multiply the value and (2020 - value) and break.
If we don't find the incoming value already as a key, we store it as key while value is set to the default (0).
"""
lines = file('input-1.txt', 'r')
arr = defaultdict(int)
for line in lines:
val = int(line)
if 2020-val in arr:
print("Result: " + str(val * (2020-val)))
break
else:
arr[val] = 0
```

If always all our values were ‘zero’, why are even considering such a datastructure?

I started with an array *for its direct facilitation of storing multiple values* and then advanced to a datastructure that *promises constant time retrieval as opposed to full iteration like in an array* that turned out to be a *HashMap (dictionary)*

The same promise can be provided by sets too. See here that the average time complexity of *search* is still O(1)

```
"""
We make up our 'arr' a Set - since we didn't have to fully utlilize any "key-value" facility in the last attempt.
All we are interested in is only one entity "key" and we still avoid the one inner loop from our first attempt.
Entries would be the values we read in.
If we find the difference of (2020 and incoming value) as an existing set constituent, simply multiply the value and (2020 - value) and break.
If we don't find the incoming value already as a key, we store it in set.
"""
lines = file('input-1.txt', 'r')
arr = set()
for line in lines:
val = int(line)
if 2020-val in arr:
print("Result: " + str(val * (2020-val)))
break
else:
arr.add(val)
```

Thanks again Ram!

- Never process anything that was already seen once
- To support that, always look for something
*better than arrays* - Do you think you will calculate something again after some time? Calculate now and store it such that
*search*takes*constant time*

- To support that, always look for something
- HashMaps are not always the answer. If you have only one piece of information to store, you just need a
*Set*- However, look at next post where we ultimately (not at the start) have to use HashMap