Spoilers ahead for the solutions of Advent of Code 2020 - Day 01 in Rust. The full solution is available here.

If you are unfamiliar, 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.

The puzzle usually has a story, but we’d be looking at the actual problem we need to solve.

Part 1: Given an array of numbers, find two values that sum to 2020. Once you find the two values, multiply them. This might sound familiar to many, and if it does - yes, its the popular Two Sum problem for folks used to leetcode-ing.

The solution looks something like this:

Part 1: Extended

Given an array of numbers, find three values that sum to 2020, and multiply them. The naive solution for this using a nested loop and then trying to find all possible triplets that sum to 2020. However, the complexity for something like that would be O(n^3) and we probably don’t want that.

A better solution could be to sort the array, and then use a Two pointer approach with a sliding window approach. The complexity for this solution would be O(n log(n)) worst case, due to the sort.