December 7, 2020

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other. — AdventOfCode.com

For this puzzle, they've given us a list of numbers as input (one number on each line).

**Problem:** Find the first two numbers that sum to **2020**. The answer is
the multplication of these two numbers.

**Solution:** We're going to iterate through the array and each time, caculate
the difference between the current number and 2020. Then add the
**difference** to a set that we have previously initialized if the **current
number** doesn't exist in the set. However, if it does exist, it means that we
have found our pair. Let's dive into the code:

`Copied!1const input = `217213979436652996675714568`;910const numbers = input11 .trim()12 .split('\n') // split on new line character13 .map((str) => +str); // turn each string to a number so it'll be easier to work with1415const part1 = () => {16 const seenDiffs: new Set<number>();1718 for (const number of numbers) {19 if (seenDiffs.has(number)) {20 return (2020 - number) * number;21 }22 seenDiffs.add(2020 - number);23 }2425 // answer not found26 return null;27};`

**Complexity:** Our time complexity is *linear* since we are only iterating
the numbers array once and look-up and insert operations are done in constant
time for sets. Worst case space complexity is also *linear* because we are
storing a whole copy of the array in the set.

**Problem:** Find the first three numbers that sum to 2020. The answer is
produced by multiplying these numbers together.

**Solution:** A good place to start is to make a function that returns a pair
of numbers or null for a given array and a target sum. Then we can iterate
through the array and use this function to see if there's a pair that sums to
our current difference. That was a handful but hopefully it will make more
sense after looking at the code:

`Copied!1const getPairForSum = (2 numbers: number[],3 sum: number,4 skipIndex?: number5) => {6 const seenDiffs: new Set<number>();78 for (const [index, number] of numbers.entries()) {9 if (skipIndex === index) continue;10 if (seenDiffs.has(number)) {11 return [sum - number, number];12 }1314 seenDiffs.add(sum - number);15 }1617 // answer not found18 return null;19};2021const part2 = () => {22 for (const [index, number] of numbers.entries()) {23 const pair = getPairForSum(numbers, 2020 - number, index);2425 if (pair) {26 return number * pair[0] * pair[1];27 }28 }2930 return null;31};`

**Complexity:** Time complexity is O(n^2) because we are doing a O(n)
operation in each iteration (calling `getPairForSum()`

). Space complexity is
O(n) (linear) because we are doing a linear operation in each iteration and
the space taken by each iteration frees up when we move on to the next
iteration.