Given an array of integers, return indices of the two numbers such that they add up to a specific target.
This is actually a problem I got during a job interview back in my first or second year of CS. When I came across it again, I instantly recognized it. Although this specific question is a little different, as I’m supposed to return the indices of the two numbers, whereas during my interview, I had to return the numbers themselves. Still, it’s basically the same question.
- Given nums = [2, 7, 11, 15], target = 9,
- Because nums + nums = 2 + 7 = 9,
- return [0, 1].
Crappy (initial) solution
So I mentioned that I got this problem before during an interview, I actually solved it and came to a solution back then, and while I don’t remember my exact code or thought process, I do remember that my approach was to just use two loops.
I added some extra printlns just to illusrate what’s happening. We’re bruteforcing and comparing every value within the array, which has a time-complexity of O(n^2).
In a random 50-element array with values between 0-50, and a target value of 15, we get the following output:
3 + 11 = 15, so we are returned the indices of 3 and 11, which happen to be 0 and 8. This works, but like my interviewer back then told me, is not even close to the most efficient solution. Believe me, we got lucky here with the input.
Better (but still crappy) solution
After some prodding and tips from the interviewer, I came to a solution that was similar to this, which involves sorting the array, this means we don’t need as many comparisons. This solution’s runtime is bound by Arrays.sort(), O(logn)
Okay so, quick disclaimer: the best way of solving this problem is to use hash tables, likely the solution my interviwer was looking for.
That’s simple enough, but a much cooler solution is to use binary search. Why? Because I learned binary-search in school and WANT TO ACTUALLY USE IT FOR SOMETHING DAMNIT! So here it is! Again, I added some extra printlns to show the number of b-searches done and to show what’s happening.
Solved with b-search:
What’s happening here is we perform a binary search for the target value minus the current value we’re at in the array. If we cannot find it, then we move to the next element in the array and try again.