AoC 2020 D1: Report Repair

| Problem statement | Source code | Tags: Brute forceData structures

Back to AoC Index Next →

Part 1

This is the classic two-sum problem, which should be familiar to anyone spending more than 5 minutes on LeetCode. A naïve solution is $\mathcal{O}(n^2)$ by checking all pairs; since the input is only 200 numbers and it is day 1, this is acceptable. A better solution is to use a hash set to store the numbers we have seen so far, and for each number, check if 2020 - number is in the set. This gives us an $\mathcal{O}(n)$ solution.

Part 2

This is yet another classic problem, three-sum. The naïve solution is $\mathcal{O}(n^3)$ by checking all triplets; at 8,000,000 operations it's a bit out of hands, bt still doable. A better solution is to enumerate all pairs and use a hash set to check if 2020 - (num1 + num2) exists. This gives us an $\mathcal{O}(n^2)$ solution.

Back to AoC Index Next →