Advent of Code — Day 1 — Javascript

Advent of Code is a series of 25 coding puzzles that are released daily between December 1 to December 25. It is free and open to everyone to participate and since it started in 2015, has grown to have a large community of thousands of users with a dedicated subreddit. In this series of blogs, I will try to solve each day’s problem set similar to how I would answer on a technical interview.

For Day 1, the problem is to find two numbers in a list that sum to 2020 and give the product of those two numbers. As there do not appear to be any constraints shown on the problem, I may ask the interviewer if there is only one answer within the dataset.

The example that the problem has provided is below:

1721
979
366
299
675
1456
Sum: 1721 + 299 = 2020
Product 1721 * 299 = 514579

The naïve solution to this problem would be to format the list into an array and create a nested ‘for’ loop and check every sum of every number and if it equals 2020, then return the product of the two numbers. Something like what is shown below:

for(let i = 0; i < arr.length; i++){
    for(let j = 0; j < arr.length; j++){
       if(arr[i] + arr[j] === 2020)
           return arr[i] * arr[k]
    }
}

A nested ‘for’ loop, however is definitely not ideal for time complexity as it is O(n²) and would likely not pass during a technical interview.

The ideal solution for this problem would be to use a Set or an Object for lookup which has O(n) time complexity.

let obj = {}
for(let i = 0; i < arr.length; i++){
    let num = 2020 - arr[i]
    if(num in obj)
        return arr[i] * num
    obj[arr[i]] = i
}

Above, we are going through each number in the array and we are getting the number that it would need to be paired with in order to add to 2020. Then we are checking if the number it is pairing with exists in the object. If the pair does not exist, we will add the original number to the object so if the pair does exist further down, it will find it.

For example, if I wanted to find two numbers that add to 10 and had an array of [2, 4, 8]. As I iterate through the array, my ‘num’ variable is 8. If I do not have a 8 in the object, I would add 2into the object: {2}. I would iterate to 4 in the array and find that it’s pair, 6 is not in the object: {2, 4}. The next iteration in the array is 8 which means I am looking for the number 2 in the object. The value of 2 does exist in the object, therefore I will return 8 * 2 = 16.