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!