Daily Coding Problem 01: Summable Numbers in an Array

I recently realized the reason I don’t write a blog about my coding journey is that I am quite convinced that everything I know is wrong. That is still true, so I’m going to be writing with that self-awareness. I’m not trying to teach anyone: I’m just writing down the way I think today so that I don’t forget things. This is a public ledger of my knowledge level today, as that’s the only way I can build upon it.

So.

As part of a new goal to start blogging, I’ll be attempting to solve some of the Daily Coding Challenges that show up in my inbox daily.

Today’s question

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

(Apparently this question was asked by Google)

My attempt

The naive way would be to look at each element of the list and compare it with each other number on the list, checking if they sum up to k.

Pseudocode for the above would be something like:

1. Take list l
2. Take initial list item l[0]
3. Take next list item l[1]
4. Is l[0] + l[1] == k?
5. If true, return
6. Else is l[0] + l[2] = k?
7. Do comparison ’til you get to l[l.length-1]
8. If no return, initial list item l[0] becomes l[1]

Necessary tweak to this algorithm would be to add a ‘continue’ instruction if l[0] and l[x] (where x is the position of the second item) are the same. This way, you can always start the second item at position l[0]

The code, in JavaScript, below:

The problem with this solution is the asymptotic complexity of O(n2). I’ll appreciate an improved solution to this problem, with exhaustive explanations if possible.

Note: I reimplemented this using the in-built for...of statement. If there was an improvement in the time complexity, I did not notice it.