Overview

First things first, I want to say sorry for not posting the last two weeks. I’ve had personal issues going on and have been working on the SwiftUI course in all of my extra time. On the bright side, my amazing girlfriend bought me a Bamboo tablet so I can now draw and explain views and algorithms in a way that I used to do at Virginia Tech! Woohoo!

Stay tuned for the first project to be released soon: Rebuilding Apple’s iOS calculator. I’m going to go into more depth on how I will be releasing the content in this course in the upcoming blogs, so make sure to read the upcoming posts because they’re going to discuss the release in more depth.

Now that the adminstrivia stuff is out of the way, let’s get to todays post!

Every day for the rest of December, or until at-least, the challenge is over, I’m going to be releasing my solution to the Advent of Code daily challenge as a blog post 🎄

I’ll go into some depth about how I solved the problem and how I thought about it, but I’ll leave it up for you to dive deeper into my solution if that’s something you would like to do. These are going to be short and sweet. I’m going to post the problem statement, list what needs to be done to solve it, and then my solution to the problem. I’m going to try to spice it up and write them in different languages (but if I’m running late they’ll most likely be in Swift or Python). Make sure to read all of them and share the solutions that you really like!

Alright, onto Day 1 of advent of code! 🍺 🎄 🎅

Problem Statement

Part 1) “Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn’t quite adding up.

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.”

For example, suppose your expense report contained the following:

1721
979
366
299
675
1456

Part 2) Same thing as part 1, except we’re looking for 3 numbers that sum up to 2020 (cough cough, nearly every FANG interview does something like this)

Problem requirements list

Both problems are going to be solved in a very similar fashion:

• Find a sum of numbers in the input array who’s total is 2020
• Return the product of these numbers

If you’ve done any coding interview prep, I’m sure this sounds very similar (Two Sum). If not, no worries! Try solving it then checkout my solution!

My solution

First, let’s get the naive solution out of the way: iterate over the array in O(n^2) time with two for loops and check to see if nums[i] + nums[j] = 2020. Although it solves the problem, let’s use a set to find a better solution.

Instead of forgetting about the numbers that we’ve seen as we do in the two for-loop answer, let’s keep track of these numbers in a set. When we traverse the array, we can then see if the set contains the number equal to 2020 - currNum. If so, we then return the product of the currNum and 2020 - currNum and return it!

def two_sum(nums, total=2020) -> int:
    seen_nums = set()
    for num in nums:
        needed_num = total - num
        if needed_num in seen_nums:
            return needed_num * num

        # add num to seen set
        seen_nums.add(num)
    # return -1 if we can't find a two_sum
    return -1

The same thing goes for 3-sum. We still can get rid of an order of magnitude of n by adding a set. Since there are three numbers we need to find, this will be O(n^2) since it would require 3 loops otherwise.

def three_sum(nums, total=2020) -> int:
    seen_nums = set()
    for i, num in enumerate(nums):
        # iterate through the numbers after the index of our current num
        for num_2 in nums[i:]:
            needed_num = total - num - num_2
            if needed_num in seen_nums:
                return needed_num * num * num_2

        # add the first num
        seen_nums.add(num)
    
    # return -1 on fail
    return -1

Wrap Up

Just like that, we’re done with Day 1! I look forward to seeing you tomorrow!

Let me know in the comments ⬇️ if you were able to come up with this solution on your own! I can’t always promise the best complexity (cause I’m not going to cheat) but if you can do better, let me know down below!

As always, if you liked today’s content, make sure you subscribe to the newsletter down below and if you want to support my coffee addiction, help me out by buying me a coffee! It keeps me going to create more AWESOME FREE CONTENT FOR YOU! Thanks for taking the time to unwrap some bytes with me. Cheers! 🍻 🎄 🎅

Shoutout to Mel Poole on Unsplash for the awesome photo!