Spaghetti with BQN

Photo by Mae Mu on Unsplash

One of the most famous problems that we all learn when we start our journey into algorithms is “Two Sum” where one is supposed to find the pair of numbers that sum up to a target value.

This problem has at least three different solutions which are widely quoted:

1. Brute Force where we check every possible combination of the elements. This has a time complexity of O(n²)
2. HashMap where we leverage a hash to to be able to do quick lookups. This has a time complexity of O(n)
3. Double Pointers where we would first sort the array and then use two pointers (one starting at the start of the list and another starting at the end of it) which we slowly bring closer to each other. This has a time complexity of O(nlogn)

How would we go about solving this problem in BQN?

Let’s dive in!

Algorithm

As always, solving this problem will require a bit of a different perspective. The algorithm I have in mind is as follows:

• Create a table using the input list (both for the x as well as the y axis) where each cell represents the sum of the row and col values
• Find the cells that are equal to the target value
• Return the row and col values